Line data Source code
1 : /* The analysis "engine".
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 : #include "analyzer/common.h"
22 :
23 : #include <zlib.h>
24 :
25 : #include "cfg.h"
26 : #include "gcc-rich-location.h"
27 : #include "gimple-iterator.h"
28 : #include "gimple-pretty-print.h"
29 : #include "cgraph.h"
30 : #include "fold-const.h"
31 : #include "digraph.h"
32 : #include "plugin.h"
33 : #include "target.h"
34 : #include "stringpool.h"
35 : #include "attribs.h"
36 : #include "tree-dfa.h"
37 : #include "gimple-predict.h"
38 : #include "context.h"
39 : #include "channels.h"
40 : #include "pretty-print-markup.h"
41 :
42 : #include "text-art/dump.h"
43 :
44 : #include "analyzer/analyzer-logging.h"
45 : #include "analyzer/call-string.h"
46 : #include "analyzer/program-point.h"
47 : #include "analyzer/store.h"
48 : #include "analyzer/region-model.h"
49 : #include "analyzer/constraint-manager.h"
50 : #include "analyzer/sm.h"
51 : #include "analyzer/pending-diagnostic.h"
52 : #include "analyzer/diagnostic-manager.h"
53 : #include "analyzer/supergraph.h"
54 : #include "analyzer/program-state.h"
55 : #include "analyzer/exploded-graph.h"
56 : #include "analyzer/exploded-path.h"
57 : #include "analyzer/analysis-plan.h"
58 : #include "analyzer/checker-path.h"
59 : #include "analyzer/state-purge.h"
60 : #include "analyzer/bar-chart.h"
61 : #include "analyzer/call-info.h"
62 : #include "analyzer/known-function-manager.h"
63 : #include "analyzer/call-summary.h"
64 : #include "analyzer/impl-sm-context.h"
65 :
66 : /* For an overview, see gcc/doc/analyzer.texi. */
67 :
68 : #if ENABLE_ANALYZER
69 :
70 : namespace ana {
71 :
72 : /* class impl_region_model_context : public region_model_context. */
73 :
74 1237475 : impl_region_model_context::
75 : impl_region_model_context (exploded_graph &eg,
76 : exploded_node *enode_for_diag,
77 : const program_state *old_state,
78 : program_state *new_state,
79 : uncertainty_t *uncertainty,
80 : path_context *path_ctxt,
81 : const gimple *stmt,
82 : bool *out_could_have_done_work)
83 1237475 : : m_eg (&eg), m_logger (eg.get_logger ()),
84 1237475 : m_enode_for_diag (enode_for_diag),
85 1237475 : m_old_state (old_state),
86 1237475 : m_new_state (new_state),
87 1237475 : m_stmt (stmt),
88 1237475 : m_ext_state (eg.get_ext_state ()),
89 1237475 : m_uncertainty (uncertainty),
90 1237475 : m_path_ctxt (path_ctxt),
91 1237475 : m_out_could_have_done_work (out_could_have_done_work)
92 : {
93 1237475 : }
94 :
95 4 : impl_region_model_context::
96 : impl_region_model_context (program_state *state,
97 : const extrinsic_state &ext_state,
98 : uncertainty_t *uncertainty,
99 : logger *logger)
100 4 : : m_eg (nullptr), m_logger (logger), m_enode_for_diag (nullptr),
101 4 : m_old_state (nullptr),
102 4 : m_new_state (state),
103 4 : m_stmt (nullptr),
104 4 : m_ext_state (ext_state),
105 4 : m_uncertainty (uncertainty),
106 4 : m_path_ctxt (nullptr),
107 4 : m_out_could_have_done_work (nullptr)
108 : {
109 4 : }
110 :
111 : bool
112 3372 : impl_region_model_context::warn_at (std::unique_ptr<pending_diagnostic> d,
113 : pending_location &&ploc)
114 : {
115 3372 : LOG_FUNC (get_logger ());
116 3372 : if (m_eg)
117 : {
118 3372 : bool terminate_path = d->terminate_path_p ();
119 3372 : if (m_eg->get_diagnostic_manager ().add_diagnostic (std::move (ploc),
120 : std::move (d)))
121 : {
122 3289 : if (m_path_ctxt
123 2290 : && terminate_path
124 883 : && flag_analyzer_suppress_followups)
125 684 : m_path_ctxt->terminate_path ();
126 : return true;
127 : }
128 : }
129 : return false;
130 3372 : }
131 :
132 : void
133 214 : impl_region_model_context::add_note (std::unique_ptr<pending_note> pn)
134 : {
135 214 : LOG_FUNC (get_logger ());
136 214 : if (m_eg)
137 214 : m_eg->get_diagnostic_manager ().add_note (std::move (pn));
138 214 : }
139 :
140 : void
141 179 : impl_region_model_context::add_event (std::unique_ptr<checker_event> event)
142 : {
143 179 : LOG_FUNC (get_logger ());
144 179 : if (m_eg)
145 179 : m_eg->get_diagnostic_manager ().add_event (std::move (event));
146 179 : }
147 :
148 : void
149 24808 : impl_region_model_context::on_svalue_leak (const svalue *sval)
150 : {
151 24808 : sval = sm_state_map::canonicalize_svalue (sval, m_ext_state);
152 247966 : for (sm_state_map *smap : m_new_state->m_checker_states)
153 173542 : smap->on_svalue_leak (sval, this);
154 24808 : }
155 :
156 : void
157 433757 : impl_region_model_context::
158 : on_liveness_change (symbolic::liveness_context &liveness_ctxt)
159 : {
160 4335397 : for (sm_state_map *smap : m_new_state->m_checker_states)
161 3034126 : smap->on_liveness_change (liveness_ctxt, m_ext_state, this);
162 433757 : }
163 :
164 : void
165 30321 : impl_region_model_context::on_unknown_change (const symbolic::value_node &val,
166 : bool is_mutable)
167 : {
168 30321 : if (auto *sval = val.dyn_cast_svalue ())
169 23639 : if (!sval->can_have_associated_state_p ())
170 : return;
171 294639 : for (sm_state_map *smap : m_new_state->m_checker_states)
172 206220 : smap->on_unknown_change (val, is_mutable, m_ext_state);
173 : }
174 :
175 : void
176 309 : impl_region_model_context::on_escaped_function (tree fndecl)
177 : {
178 309 : m_eg->on_escaped_function (fndecl);
179 309 : }
180 :
181 : uncertainty_t *
182 3667559 : impl_region_model_context::get_uncertainty ()
183 : {
184 3667559 : return m_uncertainty;
185 : }
186 :
187 : /* Purge state involving SVAL. The region_model has already been purged,
188 : so we only need to purge other state in the program_state:
189 : the sm-state. */
190 :
191 : void
192 11666 : impl_region_model_context::purge_state_involving (const symbolic::node &node)
193 : {
194 11666 : int i;
195 11666 : sm_state_map *smap;
196 93328 : FOR_EACH_VEC_ELT (m_new_state->m_checker_states, i, smap)
197 81662 : smap->purge_state_involving (node, m_ext_state);
198 11666 : }
199 :
200 : void
201 7942 : impl_region_model_context::bifurcate (std::unique_ptr<custom_edge_info> info)
202 : {
203 7942 : if (m_path_ctxt)
204 7942 : m_path_ctxt->bifurcate (std::move (info));
205 7942 : }
206 :
207 : void
208 1139 : impl_region_model_context::terminate_path ()
209 : {
210 1139 : if (m_path_ctxt)
211 1102 : return m_path_ctxt->terminate_path ();
212 : }
213 :
214 : bool
215 630998 : impl_region_model_context::
216 : get_state_map_by_name (const char *name,
217 : sm_state_map **out_smap,
218 : const state_machine **out_sm,
219 : unsigned *out_sm_idx,
220 : std::unique_ptr<sm_context> *out_sm_context)
221 : {
222 630998 : if (!m_new_state)
223 : return false;
224 :
225 626972 : unsigned sm_idx;
226 626972 : if (!m_ext_state.get_sm_idx_by_name (name, &sm_idx))
227 : return false;
228 :
229 626505 : const state_machine *sm = &m_ext_state.get_sm (sm_idx);
230 626505 : sm_state_map *new_smap = m_new_state->m_checker_states[sm_idx];
231 :
232 626505 : *out_smap = new_smap;
233 626505 : *out_sm = sm;
234 626505 : if (out_sm_idx)
235 625858 : *out_sm_idx = sm_idx;
236 626505 : if (out_sm_context)
237 : {
238 577 : const sm_state_map *old_smap = m_old_state->m_checker_states[sm_idx];
239 577 : *out_sm_context
240 577 : = std::make_unique<impl_sm_context> (*m_eg,
241 : sm_idx,
242 : *sm,
243 577 : m_enode_for_diag,
244 577 : m_old_state,
245 577 : m_new_state,
246 : old_smap,
247 : new_smap,
248 577 : m_path_ctxt,
249 1154 : false);
250 : }
251 : return true;
252 : }
253 :
254 : /* Subclass of pending_location::fixer_for_epath for finding the best stmt
255 : to report the leak at, given the emission path. */
256 :
257 : class leak_ploc_fixer_for_epath : public pending_location::fixer_for_epath
258 : {
259 : public:
260 1148 : leak_ploc_fixer_for_epath (const exploded_graph &eg, tree var)
261 1148 : : m_eg (eg), m_var (var)
262 : {}
263 :
264 : void
265 1070 : fixup_for_epath (const exploded_path &epath,
266 : pending_location &ploc) const final override
267 : {
268 1070 : logger * const logger = m_eg.get_logger ();
269 1070 : LOG_FUNC (logger);
270 :
271 : /* Handle the interprocedural case where we leak the retval at a return
272 : because the caller discards the return value. */
273 1070 : if (m_var
274 924 : && TREE_CODE (m_var) == RESULT_DECL)
275 : {
276 6 : auto &point = ploc.m_enode->get_point ();
277 12 : if (point.get_stack_depth () > 1)
278 6 : if (point.get_supernode ()->exit_p ())
279 : {
280 : /* Get the program_point for the call within the caller. */
281 6 : auto &cs = point.get_call_string ();
282 6 : auto caller_snode = cs.get_return_node_in_caller ();
283 6 : gcc_assert (caller_snode);
284 6 : program_point caller_point (caller_snode, *cs.get_parent ());
285 6 : ploc.m_event_loc_info = event_loc_info (caller_point);
286 6 : return;
287 : }
288 : }
289 :
290 : /* Handle the case where we have e.g.:
291 : | var = malloc (N);
292 : | var = NULL;
293 : which with SSA becomes e.g.:
294 : | var_0 = malloc (N);
295 : | var_1 = nullptr;
296 : and thus leads to the leak being found at the enode where "var_0" goes
297 : out of scope.
298 : Fix up the location of the leak to report it at the write of NULL. */
299 1064 : if (m_var && TREE_CODE (m_var) == SSA_NAME)
300 : {
301 696 : log_scope sentinel (logger, "looking for write to sibling SSA name");
302 : /* Locate the final write to this SSA name in the path. */
303 696 : const gimple *def_stmt = SSA_NAME_DEF_STMT (m_var);
304 :
305 696 : int idx_of_def_stmt;
306 696 : if (epath.find_stmt_backwards (def_stmt, &idx_of_def_stmt))
307 : {
308 : /* What was the next write to the underlying var
309 : after the SSA name was set? (if any). */
310 :
311 631 : for (unsigned idx = idx_of_def_stmt + 1;
312 10702 : idx < epath.m_elements.size ();
313 : ++idx)
314 : {
315 10073 : const exploded_edge *eedge = epath.m_elements[idx].m_eedge;
316 10073 : if (logger)
317 0 : logger->log ("eedge[%i]: EN %i -> EN %i",
318 : idx,
319 0 : eedge->m_src->m_index,
320 0 : eedge->m_dest->m_index);
321 10073 : const gimple *stmt = eedge->maybe_get_stmt ();
322 10073 : if (!stmt)
323 2862 : continue;
324 12910 : if (const gassign *assign = dyn_cast <const gassign *> (stmt))
325 : {
326 2839 : tree lhs = gimple_assign_lhs (assign);
327 2839 : if (TREE_CODE (lhs) == SSA_NAME
328 4655 : && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (m_var))
329 : {
330 2 : if (logger)
331 0 : logger->log ("using location 0%lx from gassign",
332 0 : assign->location);
333 2 : ploc.m_event_loc_info.m_loc = assign->location;
334 2 : return;
335 : }
336 : }
337 : }
338 : }
339 696 : }
340 :
341 : /* If the epath ends at a function exit node, the location is at
342 : the final "}". Try walking backward along EPATH, looking for a
343 : the first suitable stmt with a better location. */
344 1062 : gcc_assert (ploc.m_enode->get_supernode ());
345 1062 : const greturn *return_stmt = nullptr;
346 1062 : if (ploc.m_enode->get_supernode ()->exit_p ()
347 1062 : && has_return_stmt_p (epath, return_stmt, logger))
348 : {
349 : /* If we have "return SSA_NAME;" on EPATH, keep track of the
350 : pertinent SSA name as we walk backwards through EPATH. */
351 652 : tree retval = NULL_TREE;
352 652 : if (return_stmt)
353 652 : retval = gimple_return_retval (return_stmt);
354 :
355 652 : log_scope sentinel (logger, "walking backward along epath");
356 2701 : for (int idx = epath.m_elements.size () - 1; idx >= 0; --idx)
357 : {
358 2652 : const exploded_path::element_t &element = epath.m_elements[idx];
359 2652 : const exploded_edge *eedge = element.m_eedge;
360 2652 : if (logger)
361 : {
362 0 : logger->log ("eedge[%i]: EN %i -> EN %i",
363 : idx,
364 0 : eedge->m_src->m_index,
365 0 : eedge->m_dest->m_index);
366 0 : if (retval)
367 0 : logger->log (" retval: %qE", retval);
368 : }
369 2652 : if (auto op = eedge->maybe_get_op ())
370 : {
371 1769 : if (retval)
372 350 : if (auto phis = op->dyn_cast_phis_for_edge_op ())
373 : {
374 148 : for (auto iter : phis->get_pairs ())
375 74 : if (retval == iter.m_dst)
376 : {
377 : /* We have "PHI(RETVAL = SRC);"
378 : Track SRC instead */
379 74 : retval = iter.m_src;
380 74 : if (logger)
381 0 : logger->log ("updating retval to %qE", retval);
382 : }
383 : }
384 1769 : if (const gimple *stmt = op->maybe_get_stmt ())
385 1681 : if (consider_stmt_location_p (*stmt, retval))
386 816 : if (useful_location_p (stmt->location))
387 : {
388 603 : if (logger)
389 0 : logger->log ("using location 0x%lx from stmt",
390 0 : stmt->location);
391 603 : ploc.m_event_loc_info.m_loc = stmt->location;
392 603 : return;
393 : }
394 : }
395 : }
396 652 : }
397 1070 : }
398 :
399 : private:
400 : static bool
401 652 : has_return_stmt_p (const exploded_path &epath,
402 : const greturn *&out_greturn,
403 : logger *logger)
404 : {
405 652 : LOG_SCOPE (logger);
406 :
407 1097 : for (int idx = epath.m_elements.size () - 1; idx >= 0; --idx)
408 : {
409 1097 : const exploded_path::element_t &element = epath.m_elements[idx];
410 1097 : const exploded_edge *eedge = element.m_eedge;
411 1097 : if (eedge->m_src->get_stack_depth ()
412 2194 : != eedge->m_dest->get_stack_depth ())
413 : {
414 : /* We have interprocedural activity, and
415 : presumably are no longer in the function where
416 : EPATH terminates.
417 : Give up. */
418 : return false;
419 : }
420 1097 : if (auto op = eedge->maybe_get_op ())
421 : {
422 652 : switch (op->get_kind ())
423 : {
424 : default:
425 : break;
426 652 : case operation::kind::return_stmt:
427 652 : if (logger)
428 0 : logger->log ("found return_stmt");
429 652 : out_greturn = &((const greturn_op *)op)->get_greturn ();
430 652 : return true;
431 0 : case operation::kind::predict_stmt:
432 0 : {
433 0 : auto &stmt = ((const gimple_stmt_op *)op)->get_stmt ();
434 0 : switch (gimple_predict_predictor (&stmt))
435 : {
436 0 : case PRED_TREE_EARLY_RETURN:
437 : /* Assume this is due to a "return;" in the user's
438 : code. */
439 0 : if (logger)
440 0 : logger->log ("assuming a return: PRED_TREE_EARLY_RETURN");
441 : return true;
442 : default:
443 : break;
444 : }
445 : }
446 : break;
447 : }
448 : }
449 : }
450 : return false;
451 652 : }
452 :
453 : /* When certain statements show up on the epath of a leak
454 : at an exit node, if they have locations, these locations
455 : tend to be better locations for the leak.
456 : Return true for such statements (but without checking their
457 : locations). */
458 : static bool
459 1681 : consider_stmt_location_p (const gimple &stmt,
460 : tree retval)
461 : {
462 1681 : if (retval && TREE_CODE (retval) == SSA_NAME)
463 274 : if (&stmt == SSA_NAME_DEF_STMT (retval))
464 : return true;
465 :
466 1655 : switch (stmt.code)
467 : {
468 : default:
469 : break;
470 506 : case GIMPLE_CALL:
471 506 : {
472 506 : const gcall &call = *as_a <const gcall *> (&stmt);
473 506 : if (is_cxa_end_catch_p (call))
474 : return true;
475 : }
476 : break;
477 : case GIMPLE_PREDICT:
478 : case GIMPLE_RETURN:
479 : return true;
480 : }
481 : return false;
482 : }
483 :
484 : const exploded_graph &m_eg;
485 : tree m_var;
486 : };
487 :
488 : std::unique_ptr<pending_location::fixer_for_epath>
489 0 : make_ploc_fixer_for_epath_for_leak_diagnostic (const exploded_graph &eg,
490 : tree var)
491 : {
492 0 : return std::make_unique<leak_ploc_fixer_for_epath> (eg, var);
493 : }
494 :
495 : /* A measurement of how good EXPR is for presenting to the user, so
496 : that e.g. we can say prefer printing
497 : "leak of 'tmp.m_ptr'"
498 : over:
499 : "leak of '<unknown>'". */
500 :
501 : static int
502 20002 : readability (const_tree expr)
503 : {
504 : /* Arbitrarily-chosen "high readability" value. */
505 43662 : const int HIGH_READABILITY = 65536;
506 :
507 43662 : gcc_assert (expr);
508 43662 : switch (TREE_CODE (expr))
509 : {
510 8685 : case COMPONENT_REF:
511 8685 : case MEM_REF:
512 : /* Impose a slight readability penalty relative to that of
513 : operand 0. */
514 8685 : return readability (TREE_OPERAND (expr, 0)) - 16;
515 :
516 14083 : case SSA_NAME:
517 14083 : {
518 14083 : if (tree var = SSA_NAME_VAR (expr))
519 : {
520 8815 : if (DECL_ARTIFICIAL (var))
521 : {
522 : /* If we have an SSA name for an artificial var,
523 : only use it if it has a debug expr associated with
524 : it that fixup_tree_for_diagnostic can use. */
525 713 : if (VAR_P (var) && DECL_HAS_DEBUG_EXPR_P (var))
526 0 : return readability (DECL_DEBUG_EXPR (var)) - 1;
527 : }
528 : else
529 : {
530 : /* Slightly favor the underlying var over the SSA name to
531 : avoid having them compare equal. */
532 8102 : return readability (var) - 1;
533 : }
534 : }
535 : /* Avoid printing '<unknown>' for SSA names for temporaries. */
536 : return -1;
537 : }
538 11321 : break;
539 :
540 11321 : case PARM_DECL:
541 11321 : case VAR_DECL:
542 11321 : if (DECL_NAME (expr))
543 : return HIGH_READABILITY;
544 : else
545 : /* We don't want to print temporaries. For example, the C FE
546 : prints them as e.g. "<Uxxxx>" where "xxxx" is the low 16 bits
547 : of the tree pointer (see pp_c_tree_decl_identifier). */
548 : return -1;
549 :
550 : case RESULT_DECL:
551 : /* Printing "<return-value>" isn't ideal, but is less awful than
552 : trying to print a temporary. */
553 : return HIGH_READABILITY / 2;
554 :
555 6873 : case NOP_EXPR:
556 6873 : {
557 : /* Impose a moderate readability penalty for casts. */
558 6873 : const int CAST_PENALTY = 32;
559 6873 : return readability (TREE_OPERAND (expr, 0)) - CAST_PENALTY;
560 : }
561 :
562 : case INTEGER_CST:
563 : return HIGH_READABILITY;
564 :
565 380 : default:
566 380 : return 0;
567 : }
568 :
569 : return 0;
570 : }
571 :
572 : /* A qsort comparator for trees to sort them into most user-readable to
573 : least user-readable. */
574 :
575 : int
576 10001 : readability_comparator (const void *p1, const void *p2)
577 : {
578 10001 : path_var pv1 = *(path_var const *)p1;
579 10001 : path_var pv2 = *(path_var const *)p2;
580 :
581 10001 : const int tree_r1 = readability (pv1.m_tree);
582 10001 : const int tree_r2 = readability (pv2.m_tree);
583 :
584 : /* Favor items that are deeper on the stack and hence more recent;
585 : this also favors locals over globals. */
586 10001 : const int COST_PER_FRAME = 64;
587 10001 : const int depth_r1 = pv1.m_stack_depth * COST_PER_FRAME;
588 10001 : const int depth_r2 = pv2.m_stack_depth * COST_PER_FRAME;
589 :
590 : /* Combine the scores from the tree and from the stack depth.
591 : This e.g. lets us have a slightly penalized cast in the most
592 : recent stack frame "beat" an uncast value in an older stack frame. */
593 10001 : const int sum_r1 = tree_r1 + depth_r1;
594 10001 : const int sum_r2 = tree_r2 + depth_r2;
595 10001 : if (int cmp = sum_r2 - sum_r1)
596 : return cmp;
597 :
598 : /* Otherwise, more readable trees win. */
599 1061 : if (int cmp = tree_r2 - tree_r1)
600 : return cmp;
601 :
602 : /* Otherwise, if they have the same readability, then impose an
603 : arbitrary deterministic ordering on them. */
604 :
605 1061 : if (int cmp = TREE_CODE (pv1.m_tree) - TREE_CODE (pv2.m_tree))
606 : return cmp;
607 :
608 985 : switch (TREE_CODE (pv1.m_tree))
609 : {
610 : default:
611 : break;
612 529 : case SSA_NAME:
613 529 : if (int cmp = (SSA_NAME_VERSION (pv1.m_tree)
614 529 : - SSA_NAME_VERSION (pv2.m_tree)))
615 : return cmp;
616 : break;
617 0 : case PARM_DECL:
618 0 : case VAR_DECL:
619 0 : case RESULT_DECL:
620 0 : if (int cmp = DECL_UID (pv1.m_tree) - DECL_UID (pv2.m_tree))
621 : return cmp;
622 : break;
623 : }
624 :
625 : /* TODO: We ought to find ways of sorting such cases. */
626 : return 0;
627 : }
628 :
629 : /* Return true is SNODE is the EXIT node of a function, or is one
630 : of the final snodes within its function.
631 :
632 : Specifically, handle the final supernodes before the EXIT node,
633 : for the case of clobbers that happen immediately before exiting.
634 : We need a run of snodes leading to the return_p snode, where all edges are
635 : intraprocedural, and every snode has just one successor.
636 :
637 : We use this when suppressing leak reports at the end of "main". */
638 :
639 : static bool
640 1251 : returning_from_function_p (const supernode *snode)
641 : {
642 1251 : if (!snode)
643 : return false;
644 :
645 : unsigned count = 0;
646 : const supernode *iter = snode;
647 1965 : while (true)
648 : {
649 1965 : if (iter->exit_p ())
650 : return true;
651 1236 : if (iter->m_succs.length () != 1)
652 : return false;
653 1131 : const superedge *sedge = iter->m_succs[0];
654 :
655 1131 : if (auto op = sedge->get_op ())
656 988 : if (op->get_kind () == operation::kind::return_stmt)
657 : return true;
658 :
659 737 : iter = sedge->m_dest;
660 :
661 : /* Impose a limit to ensure we terminate for pathological cases.
662 :
663 : We only care about the final 3 nodes, due to cases like:
664 : BB:
665 : (clobber causing leak)
666 :
667 : BB:
668 : <label>:
669 : return _val;
670 :
671 : EXIT BB.*/
672 737 : if (++count > 4)
673 : return false;
674 : }
675 : }
676 :
677 : /* Find the best tree for SVAL and call SM's on_leak vfunc with it.
678 : If on_leak returns a pending_diagnostic, queue it up to be reported,
679 : so that we potentially complain about a leak of SVAL in the given STATE. */
680 :
681 : void
682 1251 : impl_region_model_context::on_state_leak (const state_machine &sm,
683 : const svalue *sval,
684 : state_machine::state_t state)
685 : {
686 1251 : logger * const logger = get_logger ();
687 1251 : LOG_SCOPE (logger);
688 1251 : if (logger)
689 : {
690 0 : logger->start_log_line ();
691 0 : logger->log_partial ("considering leak of ");
692 0 : sval->dump_to_pp (logger->get_printer (), true);
693 0 : logger->end_log_line ();
694 : }
695 :
696 1251 : if (!m_eg)
697 : return;
698 :
699 : /* m_old_state also needs to be non-NULL so that the sm_ctxt can look
700 : up the old state of SVAL. */
701 1251 : gcc_assert (m_old_state);
702 :
703 : /* SVAL has leaked within the new state: it is not used by any reachable
704 : regions.
705 : We need to convert it back to a tree, but since it's likely no regions
706 : use it, we have to find the "best" tree for it in the old_state. */
707 1251 : value_set visited;
708 1251 : path_var leaked_pv
709 1251 : = m_old_state->m_region_model->get_representative_path_var (sval,
710 : &visited,
711 : nullptr);
712 :
713 : /* Strip off top-level casts */
714 1251 : if (leaked_pv.m_tree && TREE_CODE (leaked_pv.m_tree) == NOP_EXPR)
715 458 : leaked_pv.m_tree = TREE_OPERAND (leaked_pv.m_tree, 0);
716 :
717 : /* This might be NULL; the pending_diagnostic subclasses need to cope
718 : with this. */
719 1251 : tree leaked_tree = leaked_pv.m_tree;
720 1251 : if (logger)
721 : {
722 0 : if (leaked_tree)
723 0 : logger->log ("best leaked_tree: %qE", leaked_tree);
724 : else
725 0 : logger->log ("best leaked_tree: NULL");
726 : }
727 :
728 1251 : gcc_assert (m_enode_for_diag);
729 :
730 : /* Don't complain about leaks when returning from "main". */
731 1251 : if (returning_from_function_p (m_enode_for_diag->get_supernode ()))
732 : {
733 1123 : tree fndecl = m_enode_for_diag->get_function ()->decl;
734 1123 : if (id_equal (DECL_NAME (fndecl), "main"))
735 : {
736 39 : if (logger)
737 0 : logger->log ("not reporting leak from main");
738 39 : return;
739 : }
740 : }
741 :
742 1212 : tree leaked_tree_for_diag = fixup_tree_for_diagnostic (leaked_tree);
743 1212 : std::unique_ptr<pending_diagnostic> pd = sm.on_leak (leaked_tree_for_diag,
744 : m_old_state,
745 1212 : m_new_state);
746 1212 : if (pd)
747 : {
748 1148 : pending_location ploc (get_pending_location_for_diag ());
749 1148 : ploc.m_fixer_for_epath
750 1148 : = std::make_unique<leak_ploc_fixer_for_epath> (*m_eg, leaked_tree);
751 1148 : m_eg->get_diagnostic_manager ().add_diagnostic
752 1148 : (&sm, std::move (ploc),
753 : leaked_tree_for_diag, sval, state, std::move (pd));
754 1148 : }
755 1251 : }
756 :
757 : /* Implementation of region_model_context::on_condition vfunc.
758 : Notify all state machines about the condition, which could lead to
759 : state transitions. */
760 :
761 : void
762 30617 : impl_region_model_context::on_condition (const svalue *lhs,
763 : enum tree_code op,
764 : const svalue *rhs)
765 : {
766 30617 : int sm_idx;
767 30617 : sm_state_map *smap;
768 244726 : FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
769 : {
770 214109 : const state_machine &sm = m_ext_state.get_sm (sm_idx);
771 428218 : impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
772 : m_old_state, m_new_state,
773 428218 : m_old_state->m_checker_states[sm_idx],
774 428218 : m_new_state->m_checker_states[sm_idx],
775 214109 : m_path_ctxt);
776 214109 : sm.on_condition (sm_ctxt, lhs, op, rhs);
777 214109 : }
778 30617 : }
779 :
780 : /* Implementation of region_model_context::on_bounded_ranges vfunc.
781 : Notify all state machines about the ranges, which could lead to
782 : state transitions. */
783 :
784 : void
785 5836 : impl_region_model_context::on_bounded_ranges (const svalue &sval,
786 : const bounded_ranges &ranges)
787 : {
788 5836 : int sm_idx;
789 5836 : sm_state_map *smap;
790 46688 : FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
791 : {
792 40852 : const state_machine &sm = m_ext_state.get_sm (sm_idx);
793 81704 : impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
794 : m_old_state, m_new_state,
795 81704 : m_old_state->m_checker_states[sm_idx],
796 81704 : m_new_state->m_checker_states[sm_idx],
797 40852 : m_path_ctxt);
798 40852 : sm.on_bounded_ranges (sm_ctxt, sval, ranges);
799 40852 : }
800 5836 : }
801 :
802 : /* Implementation of region_model_context::on_pop_frame vfunc.
803 : Notify all state machines about the frame being popped, which
804 : could lead to states being discarded. */
805 :
806 : void
807 27017 : impl_region_model_context::on_pop_frame (const frame_region *frame_reg)
808 : {
809 27017 : int sm_idx;
810 27017 : sm_state_map *smap;
811 215764 : FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
812 : {
813 188747 : const state_machine &sm = m_ext_state.get_sm (sm_idx);
814 188747 : sm.on_pop_frame (smap, frame_reg);
815 : }
816 27017 : }
817 :
818 : /* Implementation of region_model_context::on_phi vfunc.
819 : Notify all state machines about the phi, which could lead to
820 : state transitions. */
821 :
822 : void
823 0 : impl_region_model_context::on_phi (const gphi *phi, tree rhs)
824 : {
825 0 : int sm_idx;
826 0 : sm_state_map *smap;
827 0 : FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
828 : {
829 0 : const state_machine &sm = m_ext_state.get_sm (sm_idx);
830 0 : impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
831 : m_old_state, m_new_state,
832 0 : m_old_state->m_checker_states[sm_idx],
833 0 : m_new_state->m_checker_states[sm_idx],
834 0 : m_path_ctxt);
835 0 : sm.on_phi (sm_ctxt, phi, rhs);
836 0 : }
837 0 : }
838 :
839 : /* Implementation of region_model_context::on_unexpected_tree_code vfunc.
840 : Mark the new state as being invalid for further exploration.
841 : TODO(stage1): introduce a warning for when this occurs. */
842 :
843 : void
844 52 : impl_region_model_context::on_unexpected_tree_code (tree t,
845 : const dump_location_t &loc)
846 : {
847 52 : logger * const logger = get_logger ();
848 52 : if (logger)
849 : {
850 2 : const dump_impl_location_t &impl_loc = loc.get_impl_location ();
851 2 : const char *unknown = "<unknown>";
852 2 : logger->log ("unhandled tree code: %qs in %qs at %s:%i",
853 2 : get_tree_code_name (TREE_CODE (t)),
854 2 : impl_loc.m_function ? impl_loc.m_function : unknown,
855 2 : impl_loc.m_file ? impl_loc.m_file : unknown,
856 2 : impl_loc.m_line);
857 : }
858 52 : if (m_new_state)
859 52 : m_new_state->m_valid = false;
860 52 : }
861 :
862 : /* Implementation of region_model_context::maybe_did_work vfunc.
863 : Mark that "externally visible work" has occurred, and thus we
864 : shouldn't report an infinite loop here. */
865 :
866 : void
867 24437 : impl_region_model_context::maybe_did_work ()
868 : {
869 24437 : if (m_out_could_have_done_work)
870 23972 : *m_out_could_have_done_work = true;
871 24437 : }
872 :
873 : pending_location
874 4520 : impl_region_model_context::get_pending_location_for_diag () const
875 : {
876 4520 : if (m_stmt && useful_location_p (m_stmt->location))
877 3342 : return pending_location (m_enode_for_diag, m_stmt->location);
878 : else
879 1178 : return pending_location (m_enode_for_diag);
880 : }
881 :
882 : /* struct point_and_state. */
883 :
884 : /* Assert that this object is sane. */
885 :
886 : void
887 747360 : point_and_state::validate (const extrinsic_state &ext_state) const
888 : {
889 : /* Skip this in a release build. */
890 : #if !CHECKING_P
891 : return;
892 : #endif
893 :
894 747360 : m_point.validate ();
895 :
896 747360 : m_state.validate (ext_state);
897 :
898 : /* Verify that the callstring's model of the stack corresponds to that
899 : of the region_model. */
900 : /* They should have the same depth. */
901 1487578 : gcc_assert (m_point.get_stack_depth ()
902 : == m_state.m_region_model->get_stack_depth ());
903 : /* Check the functions in the callstring vs those in the frames
904 : at each depth. */
905 1192937 : for (const frame_region *iter_frame
906 747360 : = m_state.m_region_model->get_current_frame ();
907 1940297 : iter_frame; iter_frame = iter_frame->get_calling_frame ())
908 : {
909 1192937 : int index = iter_frame->get_index ();
910 1192937 : gcc_assert (m_point.get_function_at_depth (index)
911 : == &iter_frame->get_function ());
912 : }
913 747360 : }
914 :
915 : /* Subroutine of print_enode_indices: print a run of indices from START_IDX
916 : to END_IDX to PP, using and updating *FIRST_RUN. */
917 :
918 : static void
919 6745 : print_run (pretty_printer *pp, int start_idx, int end_idx,
920 : bool *first_run)
921 : {
922 6745 : if (!(*first_run))
923 4915 : pp_string (pp, ", ");
924 6745 : *first_run = false;
925 6745 : if (start_idx == end_idx)
926 5417 : pp_printf (pp, "EN: %i", start_idx);
927 : else
928 1328 : pp_printf (pp, "EN: %i-%i", start_idx, end_idx);
929 6745 : }
930 :
931 : /* Print the indices within ENODES to PP, collecting them as
932 : runs/singletons e.g. "EN: 4-7, EN: 20-23, EN: 42". */
933 :
934 : static void
935 1842 : print_enode_indices (pretty_printer *pp,
936 : const auto_vec<exploded_node *> &enodes)
937 : {
938 1842 : int cur_start_idx = -1;
939 1842 : int cur_finish_idx = -1;
940 1842 : bool first_run = true;
941 1842 : unsigned i;
942 1842 : exploded_node *enode;
943 11707 : FOR_EACH_VEC_ELT (enodes, i, enode)
944 : {
945 9865 : if (cur_start_idx == -1)
946 : {
947 1830 : gcc_assert (cur_finish_idx == -1);
948 1830 : cur_start_idx = cur_finish_idx = enode->m_index;
949 : }
950 : else
951 : {
952 8035 : if (enode->m_index == cur_finish_idx + 1)
953 : /* Continuation of a run. */
954 : cur_finish_idx = enode->m_index;
955 : else
956 : {
957 : /* Finish existing run, start a new one. */
958 4915 : gcc_assert (cur_start_idx >= 0);
959 4915 : gcc_assert (cur_finish_idx >= 0);
960 4915 : print_run (pp, cur_start_idx, cur_finish_idx,
961 : &first_run);
962 4915 : cur_start_idx = cur_finish_idx = enode->m_index;
963 : }
964 : }
965 : }
966 : /* Finish any existing run. */
967 1842 : if (cur_start_idx >= 0)
968 : {
969 1830 : gcc_assert (cur_finish_idx >= 0);
970 1830 : print_run (pp, cur_start_idx, cur_finish_idx,
971 : &first_run);
972 : }
973 1842 : }
974 :
975 : /* struct eg_traits::dump_args_t. */
976 :
977 : /* The <FILENAME>.eg.dot output can quickly become unwieldy if we show
978 : full details for all enodes (both in terms of CPU time to render it,
979 : and in terms of being meaningful to a human viewing it).
980 :
981 : If we show just the IDs then the resulting graph is usually viewable,
982 : but then we have to keep switching back and forth between the .dot
983 : view and other dumps.
984 :
985 : This function implements a heuristic for showing detail at the enodes
986 : that (we hope) matter, and just the ID at other enodes, fixing the CPU
987 : usage of the .dot viewer, and drawing the attention of the viewer
988 : to these enodes.
989 :
990 : Return true if ENODE should be shown in detail in .dot output.
991 : Return false if no detail should be shown for ENODE. */
992 :
993 : bool
994 515 : eg_traits::dump_args_t::show_enode_details_p (const exploded_node &enode) const
995 : {
996 : /* If the number of exploded nodes isn't too large, we may as well show
997 : all enodes in full detail in the .dot output. */
998 515 : if (m_eg.m_nodes.length ()
999 515 : <= (unsigned) param_analyzer_max_enodes_for_full_dump)
1000 : return true;
1001 :
1002 : /* Otherwise, assume that what's most interesting are state explosions,
1003 : and thus the places where this happened.
1004 : Expand enodes at program points where we hit the per-enode limit, so we
1005 : can investigate what exploded. */
1006 0 : const per_program_point_data *per_point_data
1007 0 : = m_eg.get_per_program_point_data (enode.get_point ());
1008 0 : return per_point_data->m_excess_enodes > 0;
1009 : }
1010 :
1011 : /* class exploded_node : public dnode<eg_traits>. */
1012 :
1013 : const char *
1014 15 : exploded_node::status_to_str (enum status s)
1015 : {
1016 15 : switch (s)
1017 : {
1018 0 : default: gcc_unreachable ();
1019 : case status::worklist: return "worklist";
1020 13 : case status::processed: return "processed";
1021 0 : case status::special: return "special";
1022 0 : case status::merger: return "merger";
1023 2 : case status::bulk_merged: return "bulk_merged";
1024 : }
1025 : }
1026 :
1027 : /* exploded_node's ctor. */
1028 :
1029 0 : exploded_node::exploded_node (const point_and_state &ps,
1030 : int index)
1031 0 : : m_ps (ps), m_status (status::worklist), m_index (index)
1032 : {
1033 0 : gcc_checking_assert (m_ps.get_state ().m_region_model->canonicalized_p ());
1034 0 : }
1035 :
1036 371189 : exploded_node::exploded_node (point_and_state &&ps,
1037 : int index)
1038 371189 : : m_ps (std::move (ps)), m_status (status::worklist), m_index (index)
1039 : {
1040 371189 : gcc_checking_assert (m_ps.get_state ().m_region_model->canonicalized_p ());
1041 371189 : }
1042 :
1043 : /* For use by dump_dot, get a value for the .dot "fillcolor" attribute.
1044 : Colorize by sm-state, to make it easier to see how sm-state propagates
1045 : through the exploded_graph. */
1046 :
1047 : const char *
1048 1030 : exploded_node::get_dot_fillcolor () const
1049 : {
1050 1030 : const program_state &state = get_state ();
1051 :
1052 : /* We want to be able to easily distinguish the no-sm-state case,
1053 : and to be able to distinguish cases where there's a single state
1054 : from each other.
1055 :
1056 : Sum the sm_states, and use the result to choose from a table,
1057 : modulo table-size, special-casing the "no sm-state" case. */
1058 1030 : int total_sm_state = 0;
1059 1030 : int i;
1060 1030 : sm_state_map *smap;
1061 8240 : FOR_EACH_VEC_ELT (state.m_checker_states, i, smap)
1062 : {
1063 8594 : for (sm_state_map::iterator_t iter = smap->begin ();
1064 8594 : iter != smap->end ();
1065 1384 : ++iter)
1066 1384 : total_sm_state += (*iter).second.m_state->get_id ();
1067 7210 : total_sm_state += smap->get_global_state ()->get_id ();
1068 : }
1069 :
1070 1030 : if (total_sm_state > 0)
1071 : {
1072 : /* An arbitrarily-picked collection of light colors. */
1073 768 : const char * const colors[]
1074 : = {"azure", "coral", "cornsilk", "lightblue", "yellow",
1075 : "honeydew", "lightpink", "lightsalmon", "palegreen1",
1076 : "wheat", "seashell"};
1077 768 : const int num_colors = ARRAY_SIZE (colors);
1078 768 : return colors[total_sm_state % num_colors];
1079 : }
1080 : else
1081 : /* No sm-state. */
1082 : return "lightgrey";
1083 : }
1084 :
1085 : /* Implementation of dnode::dump_dot vfunc for exploded_node. */
1086 :
1087 : void
1088 515 : exploded_node::dump_dot (graphviz_out *gv, const dump_args_t &args) const
1089 : {
1090 515 : pretty_printer *pp = gv->get_pp ();
1091 :
1092 515 : dump_dot_id (pp);
1093 515 : pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,fontname=\"Monospace\",label=\"",
1094 : get_dot_fillcolor ());
1095 515 : pp_write_text_to_stream (pp);
1096 :
1097 515 : pp_printf (pp, "EN: %i", m_index);
1098 515 : if (m_status == status::merger)
1099 12 : pp_string (pp, " (merger)");
1100 503 : else if (m_status == status::bulk_merged)
1101 0 : pp_string (pp, " (bulk merged)");
1102 515 : pp_newline (pp);
1103 :
1104 515 : if (args.show_enode_details_p (*this))
1105 : {
1106 515 : format f (true);
1107 515 : m_ps.get_point ().print (pp, f);
1108 515 : pp_newline (pp);
1109 :
1110 515 : bool show_state = true;
1111 :
1112 : /* Don't show the state if we have a single predecessor
1113 : and the state hasn't changed. */
1114 515 : if (m_preds.length () == 1
1115 507 : && get_state () == m_preds[0]->m_src->get_state ())
1116 118 : show_state = false;
1117 :
1118 515 : if (show_state)
1119 : {
1120 397 : const program_state &state = m_ps.get_state ();
1121 397 : text_art::theme *theme = global_dc->get_diagram_theme ();
1122 397 : symbolic::dump_node_tree_to_pp (state, theme, pp, true, true);
1123 397 : pp_newline (pp);
1124 : }
1125 : else
1126 : {
1127 118 : pp_string (pp, "(same state as predecessor)");
1128 118 : pp_newline (pp);
1129 : }
1130 : }
1131 :
1132 515 : dump_saved_diagnostics (pp);
1133 :
1134 515 : args.dump_extra_info (this, pp);
1135 :
1136 515 : pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
1137 :
1138 515 : pp_string (pp, "\"];\n\n");
1139 :
1140 : /* It can be hard to locate the saved diagnostics as text within the
1141 : enode nodes, so add extra nodes to the graph for each saved_diagnostic,
1142 : highlighted in red.
1143 : Compare with dump_saved_diagnostics. */
1144 515 : {
1145 515 : unsigned i;
1146 515 : const saved_diagnostic *sd;
1147 1038 : FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
1148 : {
1149 8 : sd->dump_as_dot_node (pp);
1150 :
1151 : /* Add edge connecting this enode to the saved_diagnostic. */
1152 8 : dump_dot_id (pp);
1153 8 : pp_string (pp, " -> ");
1154 8 : sd->dump_dot_id (pp);
1155 8 : pp_string (pp, " [style=\"dotted\" arrowhead=\"none\"];");
1156 8 : pp_newline (pp);
1157 : }
1158 : }
1159 :
1160 515 : pp_flush (pp);
1161 515 : }
1162 :
1163 : /* Dump any saved_diagnostics at this enode to PP. */
1164 :
1165 : void
1166 589 : exploded_node::dump_saved_diagnostics (pretty_printer *pp) const
1167 : {
1168 589 : unsigned i;
1169 589 : const saved_diagnostic *sd;
1170 601 : FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
1171 : {
1172 12 : pp_printf (pp, "DIAGNOSTIC: %s (sd: %i)",
1173 12 : sd->m_d->get_kind (), sd->get_index ());
1174 12 : pp_newline (pp);
1175 : }
1176 589 : }
1177 :
1178 : /* Dump this to PP in a form suitable for use as an id in .dot output. */
1179 :
1180 : void
1181 1584 : exploded_node::dump_dot_id (pretty_printer *pp) const
1182 : {
1183 1584 : pp_printf (pp, "exploded_node_%i", m_index);
1184 1584 : }
1185 :
1186 : /* Dump a tree-like representation of this exploded_node to stderr. */
1187 :
1188 : DEBUG_FUNCTION void
1189 0 : exploded_node::dump () const
1190 : {
1191 0 : symbolic::dump_node_tree_to_stderr<exploded_node> (*this);
1192 0 : }
1193 :
1194 : /* Dump a tree-like representation of this exploded_node to PP. */
1195 :
1196 : void
1197 0 : exploded_node::dump_to_pp (pretty_printer *pp) const
1198 : {
1199 0 : text_art::theme *theme = global_dc->get_diagram_theme ();
1200 0 : symbolic::dump_node_tree_to_pp<exploded_node> (*this, theme, pp, true, true);
1201 0 : }
1202 :
1203 : /* Dump a tree-like representation of this exploded_node to LOG. */
1204 :
1205 : void
1206 0 : exploded_node::dump_to_logger (logger &log) const
1207 : {
1208 0 : symbolic::dump_node_tree_to_logger<exploded_node> (*this, log);
1209 0 : }
1210 :
1211 : std::unique_ptr<text_art::tree_widget>
1212 0 : exploded_node::make_dump_widget (symbolic::node_dump_state &nds) const
1213 : {
1214 0 : pretty_printer pp;
1215 0 : pp_printf (&pp, "EN: %i", m_index);
1216 0 : std::unique_ptr<text_art::tree_widget> w
1217 0 : (text_art::tree_widget::make (nds, &pp));
1218 :
1219 0 : w->add_child (m_ps.get_point ().make_dump_widget (nds));
1220 0 : w->add_child (m_ps.get_state ().make_dump_widget (nds));
1221 :
1222 0 : return w;
1223 0 : }
1224 :
1225 : /* Return a new json::object of the form
1226 : {"point" : object for program_point,
1227 : "state" : object for program_state,
1228 : "status" : str,
1229 : "idx" : int}. */
1230 :
1231 : std::unique_ptr<json::object>
1232 0 : exploded_node::to_json (const extrinsic_state &ext_state) const
1233 : {
1234 0 : auto enode_obj = std::make_unique<json::object> ();
1235 :
1236 0 : enode_obj->set ("point", get_point ().to_json ());
1237 0 : enode_obj->set ("state", get_state ().to_json (ext_state));
1238 0 : enode_obj->set_string ("status", status_to_str (m_status));
1239 0 : enode_obj->set_integer ("idx", m_index);
1240 :
1241 0 : return enode_obj;
1242 : }
1243 :
1244 : } // namespace ana
1245 :
1246 : /* Return true if FNDECL has a gimple body. */
1247 : // TODO: is there a pre-canned way to do this?
1248 :
1249 : bool
1250 17617 : fndecl_has_gimple_body_p (tree fndecl)
1251 : {
1252 17617 : if (fndecl == NULL_TREE)
1253 : return false;
1254 :
1255 17617 : cgraph_node *n = cgraph_node::get (fndecl);
1256 17617 : if (!n)
1257 : return false;
1258 :
1259 17617 : return n->has_gimple_body_p ();
1260 : }
1261 :
1262 : namespace ana {
1263 :
1264 : /* Subclass of call_info for exploded edges that express
1265 : a throw or rethrow of an exception (actually a call
1266 : to __cxa_throw or __cxa_rethrow). */
1267 :
1268 : class throw_custom_edge : public call_info
1269 : {
1270 : public:
1271 224 : throw_custom_edge (const call_details &cd,
1272 : tree type,
1273 : bool is_rethrow)
1274 : : call_info (cd),
1275 224 : m_type (type),
1276 224 : m_is_rethrow (is_rethrow)
1277 : {
1278 : }
1279 :
1280 0 : void print (pretty_printer *pp) const final override
1281 : {
1282 0 : if (m_is_rethrow)
1283 : {
1284 0 : if (m_type)
1285 0 : pp_printf (pp, "rethrowing %qT", m_type);
1286 : else
1287 0 : pp_printf (pp, "rethrowing");
1288 : }
1289 : else
1290 : {
1291 0 : if (m_type)
1292 0 : pp_printf (pp, "throwing %qT", m_type);
1293 : else
1294 0 : pp_printf (pp, "throwing");
1295 : }
1296 0 : }
1297 :
1298 0 : void print_desc (pretty_printer &pp) const final override
1299 : {
1300 0 : print (&pp);
1301 0 : }
1302 :
1303 422 : bool update_model (region_model *model,
1304 : const exploded_edge *,
1305 : region_model_context *ctxt) const final override
1306 : {
1307 422 : if (m_is_rethrow)
1308 : {
1309 117 : if (auto eh_node = model->get_current_caught_exception ())
1310 84 : model->push_thrown_exception (*eh_node);
1311 : else
1312 : {
1313 : /* We have a rethrow of some unknown exception.
1314 : We don't have a good way of representing this;
1315 : leave the exception stack empty. */
1316 : }
1317 : }
1318 : else
1319 : {
1320 305 : call_details cd (get_call_details (model, ctxt));
1321 :
1322 305 : const svalue *exception_sval = cd.get_arg_svalue (0);
1323 305 : const svalue *tinfo_sval = cd.get_arg_svalue (1);
1324 305 : const svalue *destructor_sval = cd.get_arg_svalue (2);
1325 :
1326 : /* Push a new exception_node on the model's m_exception_stack. */
1327 305 : exception_node eh_node (exception_sval, tinfo_sval, destructor_sval);
1328 305 : model->push_thrown_exception (eh_node);
1329 : }
1330 :
1331 422 : return true;
1332 : }
1333 :
1334 90 : void add_events_to_path (checker_path *emission_path,
1335 : const exploded_edge &eedge,
1336 : pending_diagnostic &,
1337 : const state_transition *) const final override
1338 : {
1339 90 : const exploded_node *dst_node = eedge.m_dest;
1340 90 : const program_point &dst_point = dst_node->get_point ();
1341 90 : const int dst_stack_depth = dst_point.get_stack_depth ();
1342 :
1343 90 : const gcall &call = get_call_stmt ();
1344 :
1345 90 : emission_path->add_event
1346 90 : (std::make_unique<explicit_throw_event>
1347 90 : (event_loc_info (call.location,
1348 : dst_point.get_fndecl (),
1349 90 : dst_stack_depth),
1350 : dst_node,
1351 : call,
1352 90 : m_type,
1353 90 : m_is_rethrow));
1354 90 : }
1355 :
1356 : private:
1357 : tree m_type;
1358 : bool m_is_rethrow;
1359 : };
1360 :
1361 : /* Subclass of custom_edge_info for an exploded edge that expresses
1362 : unwinding one stack frame during exception handling. */
1363 :
1364 : class unwind_custom_edge : public custom_edge_info
1365 : {
1366 : public:
1367 6631 : unwind_custom_edge (location_t loc)
1368 6631 : : m_loc (loc)
1369 : {
1370 : }
1371 :
1372 0 : void print (pretty_printer *pp) const final override
1373 : {
1374 0 : pp_printf (pp, "unwinding frame");
1375 0 : }
1376 :
1377 6663 : bool update_model (region_model *model,
1378 : const exploded_edge *,
1379 : region_model_context *ctxt) const final override
1380 : {
1381 6663 : model->pop_frame (NULL_TREE, nullptr, ctxt, nullptr, false);
1382 6663 : return true;
1383 : }
1384 :
1385 16 : void add_events_to_path (checker_path *emission_path,
1386 : const exploded_edge &eedge,
1387 : pending_diagnostic &,
1388 : const state_transition *) const final override
1389 : {
1390 16 : const exploded_node *src_node = eedge.m_src;
1391 16 : const program_point &src_point = src_node->get_point ();
1392 16 : const int src_stack_depth = src_point.get_stack_depth ();
1393 16 : emission_path->add_event
1394 32 : (std::make_unique<unwind_event> (event_loc_info (m_loc,
1395 : src_point.get_fndecl (),
1396 16 : src_stack_depth)));
1397 16 : }
1398 :
1399 : private:
1400 : location_t m_loc;
1401 : };
1402 :
1403 : /* Locate an SNODE that's a CFG edge with the EH flag,
1404 : or return nullptr. */
1405 :
1406 : static const superedge *
1407 7565 : get_eh_outedge (const supernode &snode)
1408 : {
1409 27299 : for (auto out_sedge : snode.m_succs)
1410 6926 : if (::edge cfg_edge = out_sedge->get_any_cfg_edge ())
1411 1385 : if (cfg_edge->flags & EDGE_EH)
1412 : return out_sedge;
1413 :
1414 : // Not found
1415 : return nullptr;
1416 : }
1417 :
1418 : /* Given THROWN_ENODE, which expresses a throw or rethrow occurring at
1419 : THROW_STMT, unwind intraprocedurally and interprocedurally to find
1420 : the next eh_dispatch statement to handle exceptions, if any.
1421 :
1422 : Add eedges and enodes to this graph expressing the actions taken
1423 : to reach an enode containing the eh_dispatch stmt, if any.
1424 : Only the final enode is added to this graph's worklist.
1425 :
1426 : Use CTXT to warn about problems e.g. memory leaks due to stack frames
1427 : being unwound. */
1428 :
1429 : void
1430 6301 : exploded_graph::unwind_from_exception (exploded_node &thrown_enode,
1431 : const gimple *throw_stmt,
1432 : region_model_context *ctxt)
1433 : {
1434 6301 : logger * const logger = get_logger ();
1435 6301 : LOG_FUNC_1 (logger, "thrown EN: %i", thrown_enode.m_index);
1436 :
1437 : /* Iteratively unwind the stack looking for an out-cfg-edge
1438 : flagged EH. */
1439 6301 : exploded_node *iter_enode = &thrown_enode;
1440 6301 : while (iter_enode)
1441 : {
1442 : /* If we have an out-cfg-edge flagged EH, follow that,
1443 : presumably to a bb with a label and an eh_dispatch stmt.
1444 : Otherwise assume no out-cfgs-edges, and we are unwinding to the
1445 : caller. */
1446 7565 : if (auto sedge = get_eh_outedge (*iter_enode->get_supernode ()))
1447 : {
1448 : /* Intraprocedural case.
1449 : Assume we have an out-edge flagged with EH leading to
1450 : code for dispatch to catch handlers. */
1451 934 : const program_point next_point
1452 934 : (sedge->m_dest,
1453 934 : iter_enode->get_point ().get_call_string ());
1454 934 : exploded_node *next_enode
1455 934 : = get_or_create_node (next_point,
1456 : iter_enode->get_state (),
1457 : iter_enode,
1458 : /* Add this enode to the worklist. */
1459 : true);
1460 934 : if (!next_enode)
1461 : return;
1462 :
1463 934 : add_edge (iter_enode, next_enode, nullptr, false, nullptr);
1464 934 : return;
1465 : }
1466 : else
1467 : {
1468 : /* Interprocedural case.
1469 : No out-cfg-edge. Unwind one stack frame. */
1470 6631 : program_state unwound_state (iter_enode->get_state ());
1471 6631 : location_t loc = throw_stmt ? throw_stmt->location : UNKNOWN_LOCATION;
1472 6631 : auto unwind_edge_info
1473 6631 : = std::make_unique<unwind_custom_edge> (loc);
1474 6631 : unwind_edge_info->update_model (unwound_state.m_region_model, nullptr,
1475 : ctxt);
1476 :
1477 : /* Detect leaks in the new state relative to the old state.
1478 : Use an alternate ctxt that uses the original enode and the stmt
1479 : (if any) for the location of any diagnostics. */
1480 6631 : {
1481 6631 : uncertainty_t uncertainty;
1482 6631 : impl_region_model_context ctxt (*this,
1483 : &thrown_enode,
1484 6631 : &iter_enode->get_state (),
1485 : &unwound_state,
1486 : &uncertainty,
1487 : nullptr,
1488 6631 : throw_stmt);
1489 6631 : program_state::detect_leaks (iter_enode->get_state (),
1490 : unwound_state,
1491 : nullptr,
1492 : get_ext_state (), &ctxt);
1493 6631 : }
1494 6631 : const call_string &cs = iter_enode->get_point ().get_call_string ();
1495 6631 : if (cs.empty_p ())
1496 : {
1497 : /* Top-level stack frame in analysis: unwinding
1498 : to the outside world that called us. */
1499 : return;
1500 : }
1501 : else
1502 : {
1503 : /* Nested function in analysis: unwinding to
1504 : the callsite in the analysis (or beyond). */
1505 1671 : program_point unwound_point (cs.get_return_node_in_caller (), cs);
1506 1671 : unwound_point.pop_from_call_stack ();
1507 :
1508 1671 : exploded_node *after_unwind_enode
1509 1671 : = get_or_create_node (unwound_point,
1510 : unwound_state,
1511 : iter_enode,
1512 : /* Don't add this enode to the
1513 : worklist; we will process it
1514 : on the next iteration. */
1515 : false);
1516 :
1517 1671 : if (!after_unwind_enode)
1518 407 : return;
1519 :
1520 1264 : add_edge (iter_enode, after_unwind_enode, nullptr, true,
1521 1264 : std::move (unwind_edge_info));
1522 1264 : iter_enode = after_unwind_enode;
1523 : }
1524 6631 : }
1525 : }
1526 6301 : }
1527 :
1528 : /* Handle THROW_CALL, a call to __cxa_throw or __cxa_rethrow.
1529 :
1530 : Create an eedge and destination enode for the throw/rethrow, adding
1531 : them to this egraph. The new enode isn't added to the worklist, but
1532 : instead exploded_graph::unwind_from_exception is immediately called
1533 : on it, potentially creating more eedges and enodes leading to an
1534 : eh_handler stmt. */
1535 :
1536 : void
1537 227 : exploded_node::on_throw (exploded_graph &eg,
1538 : const gcall &throw_call,
1539 : const program_point &after_throw_point,
1540 : program_state *new_state,
1541 : bool is_rethrow,
1542 : region_model_context *ctxt)
1543 : {
1544 227 : region_model *model = new_state->m_region_model;
1545 227 : call_details cd (throw_call, model, ctxt);
1546 :
1547 227 : if (!cd.get_fndecl_for_call ())
1548 3 : return;
1549 :
1550 : /* Create an enode and eedge for the "throw". */
1551 224 : tree type = NULL_TREE;
1552 224 : if (is_rethrow)
1553 : {
1554 81 : const exception_node *eh_node = model->get_current_caught_exception ();
1555 66 : if (eh_node)
1556 66 : type = eh_node->maybe_get_type ();
1557 : else
1558 : {
1559 : /* We have a "throw;" but no exception to rethrow.
1560 : Presumably the top-level of the analysis is an
1561 : entrypoint for handling exceptions, so we will
1562 : simulate fully unwinding. */
1563 : }
1564 : }
1565 : else
1566 : {
1567 143 : const svalue *tinfo_sval = cd.get_arg_svalue (1);
1568 143 : type = tinfo_sval->maybe_get_type_from_typeinfo ();
1569 : }
1570 :
1571 224 : auto throw_edge_info
1572 224 : = std::make_unique<throw_custom_edge> (cd, type, is_rethrow);
1573 224 : throw_edge_info->update_model (model, nullptr, ctxt);
1574 :
1575 224 : exploded_node *after_throw_enode
1576 224 : = eg.get_or_create_node (after_throw_point, *new_state, this,
1577 : /* Don't add to worklist; we process
1578 : this immediately below. */
1579 : false);
1580 :
1581 224 : if (!after_throw_enode)
1582 0 : return;
1583 :
1584 : /* Create custom exploded_edge for a throw. */
1585 224 : eg.add_edge (this, after_throw_enode, nullptr, true,
1586 224 : std::move (throw_edge_info));
1587 :
1588 224 : eg.unwind_from_exception (*after_throw_enode, &throw_call, ctxt);
1589 224 : }
1590 :
1591 : /* Subroutine of exploded_graph::process_node for finding the successors
1592 : of the supernode for a function exit basic block.
1593 :
1594 : Ensure that pop_frame is called, potentially queuing diagnostics about
1595 : leaks. */
1596 :
1597 : void
1598 12171 : exploded_node::detect_leaks (exploded_graph &eg)
1599 : {
1600 12171 : LOG_FUNC_1 (eg.get_logger (), "EN: %i", m_index);
1601 :
1602 12171 : gcc_assert (get_point ().get_supernode ()->exit_p ());
1603 :
1604 : /* If we're not a "top-level" function, do nothing; pop_frame
1605 : will be called when handling the return superedge. */
1606 12171 : if (get_point ().get_stack_depth () > 1)
1607 0 : return;
1608 :
1609 : /* We have a "top-level" function. */
1610 12171 : gcc_assert (get_point ().get_stack_depth () == 1);
1611 :
1612 12171 : const program_state &old_state = get_state ();
1613 :
1614 : /* Work with a temporary copy of the state: pop the frame, and see
1615 : what leaks (via purge_unused_svalues). */
1616 12171 : program_state new_state (old_state);
1617 :
1618 12171 : gcc_assert (new_state.m_region_model);
1619 :
1620 12171 : uncertainty_t uncertainty;
1621 12171 : impl_region_model_context ctxt (eg, this,
1622 : &old_state, &new_state, &uncertainty, nullptr,
1623 12171 : nullptr);
1624 12171 : const svalue *result = nullptr;
1625 12171 : new_state.m_region_model->pop_frame (nullptr, &result, &ctxt, nullptr);
1626 12171 : program_state::detect_leaks (old_state, new_state, result,
1627 : eg.get_ext_state (), &ctxt);
1628 24342 : }
1629 :
1630 : /* Dump the successors and predecessors of this enode to OUTF. */
1631 :
1632 : void
1633 0 : exploded_node::dump_succs_and_preds (FILE *outf) const
1634 : {
1635 0 : unsigned i;
1636 0 : exploded_edge *e;
1637 0 : {
1638 0 : auto_vec<exploded_node *> preds (m_preds.length ());
1639 0 : FOR_EACH_VEC_ELT (m_preds, i, e)
1640 0 : preds.quick_push (e->m_src);
1641 0 : pretty_printer pp;
1642 0 : print_enode_indices (&pp, preds);
1643 0 : fprintf (outf, "preds: %s\n",
1644 : pp_formatted_text (&pp));
1645 0 : }
1646 0 : {
1647 0 : auto_vec<exploded_node *> succs (m_succs.length ());
1648 0 : FOR_EACH_VEC_ELT (m_succs, i, e)
1649 0 : succs.quick_push (e->m_dest);
1650 0 : pretty_printer pp;
1651 0 : print_enode_indices (&pp, succs);
1652 0 : fprintf (outf, "succs: %s\n",
1653 : pp_formatted_text (&pp));
1654 0 : }
1655 0 : }
1656 :
1657 : // class interprocedural_call : public custom_edge_info
1658 :
1659 : void
1660 8 : interprocedural_call::print (pretty_printer *pp) const
1661 : {
1662 8 : pp_string (pp, "call to ");
1663 8 : pp_gimple_stmt_1 (pp, &get_gcall (), 0, (dump_flags_t)0);
1664 8 : }
1665 :
1666 : void
1667 8 : interprocedural_call::get_dot_attrs (const char *&/*out_style*/,
1668 : const char *&out_color) const
1669 : {
1670 8 : out_color = "red";
1671 8 : }
1672 :
1673 : bool
1674 9577 : interprocedural_call::update_state (program_state *state,
1675 : const exploded_edge *eedge,
1676 : region_model_context *ctxt) const
1677 : {
1678 9577 : return update_model (state->m_region_model, eedge, ctxt);
1679 : }
1680 :
1681 : bool
1682 14799 : interprocedural_call::update_model (region_model *model,
1683 : const exploded_edge */*eedge*/,
1684 : region_model_context *ctxt) const
1685 : {
1686 14799 : model->update_for_gcall (get_gcall (), ctxt, &m_callee_fun);
1687 14799 : return true;
1688 : }
1689 :
1690 : void
1691 1397 : interprocedural_call::add_events_to_path (checker_path *emission_path,
1692 : const exploded_edge &eedge,
1693 : pending_diagnostic &pd,
1694 : const state_transition *state_trans) const
1695 : {
1696 1420 : pd.add_call_event (eedge, get_gcall (), *emission_path,
1697 : (state_trans
1698 23 : ? state_trans->dyn_cast_state_transition_at_call ()
1699 : : nullptr));
1700 1397 : }
1701 :
1702 : bool
1703 1292 : interprocedural_call::try_to_rewind_data_flow (rewind_context &ctxt) const
1704 : {
1705 1292 : auto logger = ctxt.m_logger;
1706 :
1707 : // Rewind from params to arguments
1708 1292 : if (ctxt.m_input.m_region_holding_value)
1709 : {
1710 58 : const region_model &dst_enode_model = ctxt.get_dst_region_model ();
1711 58 : tree dst_tree
1712 : = dst_enode_model.get_representative_tree
1713 58 : (ctxt.m_input.m_region_holding_value);
1714 58 : if (dst_tree)
1715 : {
1716 52 : callsite_expr expr;
1717 52 : tree src_tree
1718 52 : = m_op.map_expr_from_callee_to_caller (m_callee_fun.decl,
1719 : dst_tree,
1720 : &expr);
1721 52 : if (src_tree)
1722 : {
1723 23 : const region_model &src_enode_model = ctxt.get_src_region_model ();
1724 23 : ctxt.m_output.m_region_holding_value
1725 23 : = src_enode_model.get_lvalue (src_tree, nullptr);
1726 :
1727 23 : ctxt.add_state_transition
1728 23 : (std::make_unique<state_transition_at_call> (expr));
1729 :
1730 23 : if (logger)
1731 : {
1732 0 : callsite_expr_element e (expr);
1733 0 : logger->log ("updating m_region_holding_value from %qE to %qE"
1734 : " (callsite_expr: %e)",
1735 : dst_tree, src_tree, &e);
1736 0 : }
1737 : }
1738 : }
1739 : }
1740 :
1741 1292 : return true;
1742 : }
1743 :
1744 : const gcall &
1745 16204 : interprocedural_call::get_gcall () const
1746 : {
1747 16204 : return m_op.get_gcall ();
1748 : }
1749 :
1750 : // class interprocedural_return : public custom_edge_info
1751 :
1752 : void
1753 16 : interprocedural_return::print (pretty_printer *pp) const
1754 : {
1755 16 : pp_string (pp, "return from ");
1756 16 : pp_gimple_stmt_1 (pp, &m_call_stmt, 0, (dump_flags_t)0);
1757 16 : }
1758 :
1759 : void
1760 8 : interprocedural_return::get_dot_attrs (const char *&/*out_style*/,
1761 : const char *&out_color) const
1762 : {
1763 8 : out_color = "green";
1764 8 : }
1765 :
1766 : bool
1767 8193 : interprocedural_return::update_state (program_state *state,
1768 : const exploded_edge *eedge,
1769 : region_model_context *ctxt) const
1770 : {
1771 8193 : return update_model (state->m_region_model, eedge, ctxt);
1772 : }
1773 :
1774 : bool
1775 11050 : interprocedural_return::update_model (region_model *model,
1776 : const exploded_edge */*eedge*/,
1777 : region_model_context *ctxt) const
1778 : {
1779 11050 : model->update_for_return_gcall (m_call_stmt, ctxt);
1780 11050 : return true;
1781 : }
1782 :
1783 : void
1784 818 : interprocedural_return::add_events_to_path (checker_path *emission_path,
1785 : const exploded_edge &eedge,
1786 : pending_diagnostic &,
1787 : const state_transition *state_trans) const
1788 : {
1789 818 : const program_point &dst_point = eedge.m_dest->get_point ();
1790 818 : emission_path->add_event
1791 818 : (std::make_unique<return_event>
1792 818 : (eedge,
1793 1636 : event_loc_info (m_call_stmt.location,
1794 : dst_point.get_fndecl (),
1795 1636 : dst_point.get_stack_depth ()),
1796 : (state_trans
1797 818 : ? state_trans->dyn_cast_state_transition_at_return ()
1798 : : nullptr)));
1799 818 : }
1800 :
1801 : bool
1802 778 : interprocedural_return::try_to_rewind_data_flow (rewind_context &ctxt) const
1803 : {
1804 778 : auto logger = ctxt.m_logger;
1805 :
1806 778 : tree lhs = gimple_call_lhs (&m_call_stmt);
1807 778 : if (!lhs)
1808 : return true;
1809 :
1810 445 : const region_model &src_enode_model = ctxt.get_src_region_model ();
1811 445 : tree fndecl = src_enode_model.get_current_function ()->decl;
1812 445 : tree fn_result = DECL_RESULT (fndecl);
1813 :
1814 445 : ctxt.on_data_flow (DECL_RESULT (fndecl), lhs);
1815 :
1816 445 : return true;
1817 : }
1818 :
1819 : /* class exploded_edge : public dedge<eg_traits>. */
1820 :
1821 : /* exploded_edge's ctor. */
1822 :
1823 383640 : exploded_edge::exploded_edge (exploded_node *src, exploded_node *dest,
1824 : const superedge *sedge, bool could_do_work,
1825 : std::unique_ptr<custom_edge_info> custom_info)
1826 383640 : : dedge<eg_traits> (src, dest), m_sedge (sedge),
1827 383640 : m_custom_info (std::move (custom_info)),
1828 383640 : m_could_do_work_p (could_do_work)
1829 : {
1830 383640 : }
1831 :
1832 : /* Implementation of dedge::dump_dot vfunc for exploded_edge.
1833 : Use the label of the underlying superedge, if any. */
1834 :
1835 : void
1836 523 : exploded_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const
1837 : {
1838 523 : pretty_printer *pp = gv->get_pp ();
1839 :
1840 523 : m_src->dump_dot_id (pp);
1841 523 : pp_string (pp, " -> ");
1842 523 : m_dest->dump_dot_id (pp);
1843 523 : dump_dot_label (pp);
1844 523 : }
1845 :
1846 : /* Second half of exploded_edge::dump_dot. This is split out
1847 : for use by trimmed_graph::dump_dot and base_feasible_edge::dump_dot. */
1848 :
1849 : void
1850 593 : exploded_edge::dump_dot_label (pretty_printer *pp) const
1851 : {
1852 593 : const char *style = "\"solid,bold\"";
1853 593 : const char *color = "black";
1854 593 : int weight = 10;
1855 593 : const char *constraint = "true";
1856 :
1857 593 : if (m_sedge)
1858 : {
1859 547 : if (m_sedge->get_op ())
1860 434 : style = "\"solid\"";
1861 : else
1862 113 : style = "\"dotted\"";
1863 : }
1864 593 : if (m_custom_info)
1865 22 : m_custom_info->get_dot_attrs (style, color);
1866 :
1867 593 : pp_printf (pp,
1868 : (" [style=%s, color=%s, weight=%d, constraint=%s,"
1869 : " headlabel=\""),
1870 : style, color, weight, constraint);
1871 593 : pp_flush (pp);
1872 :
1873 593 : if (m_sedge)
1874 547 : m_sedge->dump_label_to_pp (pp, false);
1875 46 : else if (m_custom_info)
1876 14 : m_custom_info->print (pp);
1877 :
1878 1148 : pp_printf (pp, "%s",
1879 593 : could_do_work_p () ? "(could do work)" : "DOES NO WORK");
1880 :
1881 593 : pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
1882 :
1883 593 : pp_printf (pp, "\"];\n");
1884 593 : }
1885 :
1886 : /* Return a new json::object of the form
1887 : {"src_idx": int, the index of the source exploded edge,
1888 : "dst_idx": int, the index of the destination exploded edge,
1889 : "sedge": (optional) object for the superedge, if any,
1890 : "custom": (optional) str, a description, if this is a custom edge}. */
1891 :
1892 : std::unique_ptr<json::object>
1893 0 : exploded_edge::to_json () const
1894 : {
1895 0 : auto eedge_obj = std::make_unique<json::object> ();
1896 0 : eedge_obj->set_integer ("src_idx", m_src->m_index);
1897 0 : eedge_obj->set_integer ("dst_idx", m_dest->m_index);
1898 0 : if (m_sedge)
1899 0 : eedge_obj->set ("sedge", m_sedge->to_json ());
1900 0 : if (m_custom_info)
1901 : {
1902 0 : pretty_printer pp;
1903 0 : pp_format_decoder (&pp) = default_tree_printer;
1904 0 : m_custom_info->print (&pp);
1905 0 : eedge_obj->set_string ("custom", pp_formatted_text (&pp));
1906 0 : }
1907 0 : return eedge_obj;
1908 : }
1909 :
1910 : const gimple *
1911 24623 : exploded_edge::maybe_get_stmt () const
1912 : {
1913 24623 : auto op = maybe_get_op ();
1914 24623 : if (!op)
1915 : return nullptr;
1916 19348 : return op->maybe_get_stmt ();
1917 : }
1918 :
1919 : const operation *
1920 64635 : exploded_edge::maybe_get_op () const
1921 : {
1922 64635 : if (!m_sedge)
1923 : return nullptr;
1924 58787 : return m_sedge->get_op ();
1925 : }
1926 :
1927 : /* A way to export the exploded_graph as a diagnostics::digraphs::digraph,
1928 : and thus to export it to SARIF diagnostic sinks. */
1929 :
1930 : class exploded_graph_diagnostic_digraph : public diagnostics::digraphs::digraph
1931 : {
1932 : public:
1933 1 : exploded_graph_diagnostic_digraph (const exploded_graph &eg)
1934 1 : : m_eg (eg)
1935 : {
1936 1 : set_graph_kind ("exploded_graph");
1937 :
1938 1 : int i;
1939 1 : exploded_node *n;
1940 17 : FOR_EACH_VEC_ELT (m_eg.m_nodes, i, n)
1941 15 : add_node_for_enode (*n);
1942 :
1943 : exploded_edge *e;
1944 15 : FOR_EACH_VEC_ELT (m_eg.m_edges, i, e)
1945 14 : add_edge_for_eedge (*e);
1946 :
1947 1 : const json::json_property worklist_prop
1948 1 : ("gcc/analyzer/exploded_graph/worklist");
1949 1 : set_property (worklist_prop,
1950 1 : m_eg.get_worklist ().to_json ());
1951 :
1952 : /* The following are global, rather than part of the
1953 : exploded graph; we add them as part of the exploded graph's
1954 : diagnostic digraph for convenience. */
1955 :
1956 : // TODO: analysis_plan
1957 :
1958 1 : const json::json_property diagnostic_manager_prop
1959 1 : ("gcc/analyzer/diagnostic_manager");
1960 1 : set_property (diagnostic_manager_prop,
1961 1 : m_eg.get_diagnostic_manager ().to_json ());
1962 :
1963 1 : auto model_mgr = m_eg.get_ext_state ().get_model_manager ();
1964 :
1965 1 : const json::json_property known_functions_prop
1966 1 : ("gcc/analyzer/known_functions");
1967 1 : set_property (known_functions_prop,
1968 1 : model_mgr->get_known_function_manager ()->to_json ());
1969 :
1970 1 : const json::json_property ext_state_prop
1971 1 : ("gcc/analyzer/extrinsic_state");
1972 1 : set_property (ext_state_prop,
1973 1 : m_eg.get_ext_state ().to_json ());
1974 1 : }
1975 :
1976 : private:
1977 : void
1978 15 : add_node_for_enode (const exploded_node &enode)
1979 : {
1980 15 : pretty_printer pp;
1981 15 : enode.dump_dot_id (&pp);
1982 15 : auto node_for_enode
1983 : = std::make_unique<diagnostics::digraphs::node> (*this,
1984 15 : pp_formatted_text (&pp));
1985 :
1986 15 : if (auto fun = enode.get_function ())
1987 14 : node_for_enode->set_logical_loc
1988 14 : (tree_logical_location_manager::key_from_tree (fun->decl));
1989 29 : node_for_enode->set_physical_loc (enode.get_location ());
1990 :
1991 15 : auto &point = enode.get_point ();
1992 15 : if (auto snode = point.get_supernode ())
1993 : {
1994 14 : const json::string_property enode_prop_supernode
1995 14 : ("gcc/analyzer/exploded_node/supernode");
1996 14 : pretty_printer pp;
1997 14 : snode->dump_dot_id (&pp);
1998 14 : node_for_enode->set_property
1999 14 : (enode_prop_supernode,
2000 : pp_formatted_text (&pp));
2001 14 : }
2002 :
2003 15 : auto &cs = point.get_call_string ();
2004 15 : auto cs_arr = std::make_unique<json::array> ();
2005 30 : for (int i = 0; i < cs.length (); ++i)
2006 : {
2007 0 : auto e = cs[i];
2008 0 : auto obj = std::make_unique<json::object> ();
2009 :
2010 0 : {
2011 0 : pretty_printer pp;
2012 0 : e.m_call_sedge->m_src->dump_dot_id (&pp);
2013 0 : obj->set_string ("source supernode", pp_formatted_text (&pp));
2014 0 : }
2015 0 : {
2016 0 : pretty_printer pp;
2017 0 : e.m_call_sedge->m_dest->dump_dot_id (&pp);
2018 0 : obj->set_string ("destination supernode", pp_formatted_text (&pp));
2019 0 : }
2020 0 : {
2021 0 : pretty_printer pp;
2022 0 : pp_format_decoder (&pp) = default_tree_printer;
2023 0 : e.m_call_op->print_as_edge_label (&pp, false);
2024 0 : obj->set_string ("call operation", pp_formatted_text (&pp));
2025 0 : }
2026 0 : cs_arr->append (std::move (obj));
2027 0 : }
2028 15 : const json::json_property enode_prop_call_string
2029 15 : ("gcc/analyzer/exploded_node/call_string");
2030 15 : node_for_enode->set_property (enode_prop_call_string,
2031 15 : std::move (cs_arr));
2032 :
2033 15 : const json::json_property enode_prop_program_state
2034 15 : ("gcc/analyzer/exploded_node/program_state");
2035 15 : node_for_enode->set_property
2036 15 : (enode_prop_program_state,
2037 15 : enode.get_state ().to_json (m_eg.get_ext_state ()));
2038 :
2039 15 : const json::string_property enode_prop_status
2040 15 : ("gcc/analyzer/exploded_node/status");
2041 15 : node_for_enode->set_property
2042 15 : (enode_prop_status,
2043 : exploded_node::status_to_str (enode.get_status ()));
2044 :
2045 15 : m_node_for_enode.insert ({&enode, node_for_enode.get ()});
2046 15 : add_node (std::move (node_for_enode));
2047 15 : }
2048 :
2049 : void
2050 14 : add_edge_for_eedge (const exploded_edge &eedge)
2051 : {
2052 14 : diagnostics::digraphs::node *src_node
2053 14 : = get_node_for_enode (eedge.m_src);
2054 14 : diagnostics::digraphs::node *dst_node
2055 14 : = get_node_for_enode (eedge.m_dest);
2056 14 : auto e = std::make_unique<diagnostics::digraphs::edge> (*this,
2057 28 : nullptr,
2058 : *src_node,
2059 14 : *dst_node);
2060 14 : if (auto *sedge = eedge.m_sedge)
2061 : {
2062 13 : const json::string_property eedge_prop_superedge
2063 13 : ("gcc/analyzer/exploded_edge/superedge");
2064 13 : pretty_printer pp;
2065 13 : pp_format_decoder (&pp) = default_tree_printer;
2066 13 : sedge->dump_label_to_pp (&pp, false);
2067 13 : e->set_property (eedge_prop_superedge,
2068 : pp_formatted_text (&pp));
2069 13 : }
2070 14 : if (auto *custom_info = eedge.m_custom_info.get ())
2071 : {
2072 0 : const json::string_property eedge_prop_custom_edge_info
2073 0 : ("gcc/analyzer/exploded_edge/custom_edge_info");
2074 0 : pretty_printer pp;
2075 0 : pp_format_decoder (&pp) = default_tree_printer;
2076 0 : custom_info->print (&pp);
2077 0 : e->set_property (eedge_prop_custom_edge_info,
2078 : pp_formatted_text (&pp));
2079 0 : }
2080 14 : add_edge (std::move (e));
2081 14 : }
2082 :
2083 : diagnostics::digraphs::node *
2084 28 : get_node_for_enode (const exploded_node *enode)
2085 : {
2086 28 : auto iter = m_node_for_enode.find (enode);
2087 28 : gcc_assert (iter != m_node_for_enode.end ());
2088 28 : return iter->second;
2089 : }
2090 :
2091 : const exploded_graph &m_eg;
2092 : std::map<const exploded_node *,
2093 : diagnostics::digraphs::node *> m_node_for_enode;
2094 : };
2095 :
2096 : std::unique_ptr<diagnostics::digraphs::digraph>
2097 1 : exploded_graph::make_diagnostics_digraph () const
2098 : {
2099 1 : return std::make_unique<exploded_graph_diagnostic_digraph> (*this);
2100 : }
2101 :
2102 : /* struct stats. */
2103 :
2104 : /* stats' ctor. */
2105 :
2106 30357 : stats::stats (int num_supernodes)
2107 30357 : : m_num_nodes (0),
2108 30357 : m_node_reuse_count (0),
2109 30357 : m_node_reuse_after_merge_count (0),
2110 30357 : m_num_supernodes (num_supernodes)
2111 : {
2112 30357 : }
2113 :
2114 : /* Log these stats in multiline form to LOGGER. */
2115 :
2116 : void
2117 11 : stats::log (logger *logger) const
2118 : {
2119 11 : gcc_assert (logger);
2120 11 : logger->log ("m_num_nodes: %i", m_num_nodes);
2121 11 : logger->log ("m_node_reuse_count: %i", m_node_reuse_count);
2122 11 : logger->log ("m_node_reuse_after_merge_count: %i",
2123 11 : m_node_reuse_after_merge_count);
2124 11 : }
2125 :
2126 : /* Dump these stats in multiline form to OUT. */
2127 :
2128 : void
2129 0 : stats::dump (FILE *out) const
2130 : {
2131 0 : fprintf (out, "m_num_nodes: %i\n", m_num_nodes);
2132 0 : fprintf (out, "m_node_reuse_count: %i\n", m_node_reuse_count);
2133 0 : fprintf (out, "m_node_reuse_after_merge_count: %i\n",
2134 0 : m_node_reuse_after_merge_count);
2135 :
2136 0 : if (m_num_supernodes > 0)
2137 0 : fprintf (out, "enodes per supernode: %.2f\n",
2138 0 : (float)m_num_nodes / (float)m_num_supernodes);
2139 0 : }
2140 :
2141 : /* Return the total number of enodes recorded within this object. */
2142 :
2143 : int
2144 6 : stats::get_total_enodes () const
2145 : {
2146 6 : return m_num_nodes;
2147 : }
2148 :
2149 : /* struct per_function_data. */
2150 :
2151 351 : per_function_data::~per_function_data ()
2152 : {
2153 1495 : for (auto iter : m_summaries)
2154 442 : delete iter;
2155 351 : }
2156 :
2157 : void
2158 442 : per_function_data::add_call_summary (exploded_node *node)
2159 : {
2160 442 : m_summaries.safe_push (new call_summary (this, node));
2161 442 : }
2162 :
2163 : /* strongly_connected_components's ctor. Tarjan's SCC algorithm. */
2164 :
2165 3573 : strongly_connected_components::
2166 : strongly_connected_components (const supergraph &sg, logger *logger)
2167 7142 : : m_sg (sg), m_per_node (m_sg.m_nodes.length ())
2168 : {
2169 3573 : LOG_SCOPE (logger);
2170 3573 : auto_timevar tv (TV_ANALYZER_SCC);
2171 :
2172 208587 : for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
2173 201441 : m_per_node.quick_push (per_node_data ());
2174 :
2175 212152 : for (auto snode : m_sg.m_nodes)
2176 201441 : if (m_per_node[snode->m_id].m_id == -1)
2177 11661 : strong_connect (snode->m_id, logger);
2178 :
2179 3573 : if (0)
2180 : dump ();
2181 3573 : }
2182 :
2183 : /* Dump this object to stderr. */
2184 :
2185 : DEBUG_FUNCTION void
2186 0 : strongly_connected_components::dump () const
2187 : {
2188 0 : fprintf (stderr, "Stack: [");
2189 0 : bool first = true;
2190 0 : for (auto i : m_stack)
2191 : {
2192 0 : if (first)
2193 : first = false;
2194 : else
2195 0 : fprintf (stderr, ", ");
2196 0 : fprintf (stderr, "%i", i);
2197 : }
2198 0 : fprintf (stderr, "]\n");
2199 0 : for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
2200 : {
2201 0 : const per_node_data &v = m_per_node[i];
2202 0 : fprintf (stderr, "SN %lu: index: %i lowlink: %i on_stack: %i\n",
2203 0 : i, v.m_id, v.m_lowlink, v.m_on_stack);
2204 : }
2205 0 : }
2206 :
2207 : /* Return a new json::array of per-snode SCC ids. */
2208 :
2209 : std::unique_ptr<json::array>
2210 1 : strongly_connected_components::to_json () const
2211 : {
2212 1 : auto scc_arr = std::make_unique<json::array> ();
2213 12 : for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
2214 10 : scc_arr->append (std::make_unique<json::integer_number> (get_scc_id (i)));
2215 1 : return scc_arr;
2216 : }
2217 :
2218 : /* Subroutine of strongly_connected_components's ctor, part of Tarjan's
2219 : SCC algorithm. */
2220 :
2221 : void
2222 201441 : strongly_connected_components::strong_connect (unsigned id,
2223 : logger *logger)
2224 : {
2225 201441 : supernode *v_snode = m_sg.m_nodes[id];
2226 201441 : if (!v_snode)
2227 201441 : return;
2228 :
2229 : /* Set the depth index for v to the smallest unused index. */
2230 201441 : per_node_data *v = &m_per_node[id];
2231 201441 : v->m_id = id;
2232 201441 : v->m_lowlink = id;
2233 201441 : m_stack.safe_push (id);
2234 201441 : v->m_on_stack = true;
2235 201441 : id++;
2236 :
2237 : /* Consider successors of v. */
2238 201441 : unsigned i;
2239 201441 : superedge *sedge;
2240 401724 : FOR_EACH_VEC_ELT (v_snode->m_succs, i, sedge)
2241 : {
2242 200283 : supernode *w_snode = sedge->m_dest;
2243 200283 : per_node_data *w = &m_per_node[w_snode->m_id];
2244 200283 : if (w->m_id == -1)
2245 : {
2246 : /* Successor w has not yet been visited; recurse on it. */
2247 189780 : strong_connect (w_snode->m_id, logger);
2248 189780 : v->m_lowlink = MIN (v->m_lowlink, w->m_lowlink);
2249 : }
2250 10503 : else if (w->m_on_stack)
2251 : {
2252 : /* Successor w is in stack S and hence in the current SCC
2253 : If w is not on stack, then (v, w) is a cross-edge in the DFS
2254 : tree and must be ignored. */
2255 2194 : v->m_lowlink = MIN (v->m_lowlink, w->m_id);
2256 : }
2257 : }
2258 :
2259 : /* If v is a root node, pop the stack and generate an SCC. */
2260 :
2261 201441 : if (v->m_lowlink == v->m_id)
2262 : {
2263 185027 : if (logger)
2264 50 : logger->log ("got SCC root node: SN %i", v->m_id);
2265 201441 : per_node_data *w;
2266 201441 : do {
2267 201441 : int id = m_stack.pop ();
2268 201441 : w = &m_per_node[id];
2269 201441 : w->m_on_stack = false;
2270 201441 : if (logger)
2271 80 : logger->log (" popping SN %i", w->m_id);
2272 201441 : } while (w != v);
2273 : }
2274 : }
2275 :
2276 : /* worklist's ctor. */
2277 :
2278 3573 : worklist::worklist (const exploded_graph &eg, const analysis_plan &plan)
2279 3573 : : m_scc (eg.get_supergraph (), eg.get_logger ()),
2280 3573 : m_plan (plan),
2281 3573 : m_queue (key_t (*this, nullptr))
2282 : {
2283 3573 : }
2284 :
2285 : /* Return the number of nodes in the worklist. */
2286 :
2287 : unsigned
2288 349992 : worklist::length () const
2289 : {
2290 349992 : return m_queue.nodes ();
2291 : }
2292 :
2293 : /* Return the next node in the worklist, removing it. */
2294 :
2295 : exploded_node *
2296 362778 : worklist::take_next ()
2297 : {
2298 362778 : return m_queue.extract_min ();
2299 : }
2300 :
2301 : /* Return the next node in the worklist without removing it. */
2302 :
2303 : exploded_node *
2304 387406 : worklist::peek_next ()
2305 : {
2306 387406 : return m_queue.min ();
2307 : }
2308 :
2309 : /* Add ENODE to the worklist. */
2310 :
2311 : void
2312 363699 : worklist::add_node (exploded_node *enode)
2313 : {
2314 363699 : gcc_assert (enode->get_status () == exploded_node::status::worklist);
2315 363699 : m_queue.insert (key_t (*this, enode), enode);
2316 363699 : }
2317 :
2318 : /* Comparator for implementing worklist::key_t comparison operators.
2319 : Return negative if KA is before KB
2320 : Return positive if KA is after KB
2321 : Return 0 if they are equal.
2322 :
2323 : The ordering of the worklist is critical for performance and for
2324 : avoiding node explosions. Ideally we want all enodes at a CFG join-point
2325 : with the same callstring to be sorted next to each other in the worklist
2326 : so that a run of consecutive enodes can be merged and processed "in bulk"
2327 : rather than individually or pairwise, minimizing the number of new enodes
2328 : created. */
2329 :
2330 : int
2331 1307074 : worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb)
2332 : {
2333 1307074 : const program_point &point_a = ka.m_enode->get_point ();
2334 1307074 : const program_point &point_b = kb.m_enode->get_point ();
2335 1307074 : const call_string &call_string_a = point_a.get_call_string ();
2336 1307074 : const call_string &call_string_b = point_b.get_call_string ();
2337 :
2338 : /* Order empty-callstring points with different functions based on the
2339 : analysis_plan, so that we generate summaries before they are used. */
2340 1307074 : if (flag_analyzer_call_summaries
2341 100408 : && call_string_a.empty_p ()
2342 88760 : && call_string_b.empty_p ()
2343 88760 : && point_a.get_function () != nullptr
2344 88379 : && point_b.get_function () != nullptr
2345 1395453 : && point_a.get_function () != point_b.get_function ())
2346 : {
2347 41390 : if (int cmp = ka.m_worklist.m_plan.cmp_function (point_a.get_function (),
2348 : point_b.get_function ()))
2349 : return cmp;
2350 : }
2351 :
2352 : /* Sort by callstring, so that nodes with deeper call strings are processed
2353 : before those with shallower call strings.
2354 : If we have
2355 : splitting BB
2356 : / \
2357 : / \
2358 : fn call no fn call
2359 : \ /
2360 : \ /
2361 : join BB
2362 : then we want the path inside the function call to be fully explored up
2363 : to the return to the join BB before we explore on the "no fn call" path,
2364 : so that both enodes at the join BB reach the front of the worklist at
2365 : the same time and thus have a chance of being merged. */
2366 1265684 : int cs_cmp = call_string::cmp (call_string_a, call_string_b);
2367 1265684 : if (cs_cmp)
2368 : return cs_cmp;
2369 :
2370 : /* Order by SCC. */
2371 1066004 : int scc_id_a = ka.get_scc_id (ka.m_enode);
2372 1066004 : int scc_id_b = kb.get_scc_id (kb.m_enode);
2373 1066004 : if (scc_id_a != scc_id_b)
2374 941455 : return scc_id_a - scc_id_b;
2375 :
2376 : /* If in same SCC, order by supernode index (an arbitrary but stable
2377 : ordering). */
2378 124549 : const supernode *snode_a = ka.m_enode->get_supernode ();
2379 124549 : const supernode *snode_b = kb.m_enode->get_supernode ();
2380 124549 : if (snode_a == nullptr)
2381 : {
2382 0 : if (snode_b != nullptr)
2383 : /* One is nullptr. */
2384 : return -1;
2385 : else
2386 : /* Both are nullptr. */
2387 0 : return 0;
2388 : }
2389 124549 : if (snode_b == nullptr)
2390 : /* One is nullptr. */
2391 : return 1;
2392 : /* Neither are nullptr. */
2393 120986 : gcc_assert (snode_a && snode_b);
2394 120986 : if (snode_a->m_bb->index != snode_b->m_bb->index)
2395 16255 : return snode_a->m_bb->index - snode_b->m_bb->index;
2396 104731 : if (snode_a->m_id != snode_b->m_id)
2397 7741 : return snode_a->m_id - snode_b->m_id;
2398 :
2399 96990 : gcc_assert (snode_a == snode_b);
2400 :
2401 : /* Otherwise, we ought to have the same program_point. */
2402 96990 : gcc_assert (point_a == point_b);
2403 :
2404 : const program_state &state_a = ka.m_enode->get_state ();
2405 : const program_state &state_b = kb.m_enode->get_state ();
2406 :
2407 : /* Sort by sm-state, so that identical sm-states are grouped
2408 : together in the worklist. */
2409 384085 : for (unsigned sm_idx = 0; sm_idx < state_a.m_checker_states.length ();
2410 : ++sm_idx)
2411 : {
2412 346306 : sm_state_map *smap_a = state_a.m_checker_states[sm_idx];
2413 346306 : sm_state_map *smap_b = state_b.m_checker_states[sm_idx];
2414 :
2415 346306 : if (int smap_cmp = sm_state_map::cmp (*smap_a, *smap_b))
2416 : return smap_cmp;
2417 : }
2418 :
2419 : /* Otherwise, we have two enodes at the same program point but with
2420 : different states. We don't have a good total ordering on states,
2421 : so order them by enode index, so that we have at least have a
2422 : stable sort. */
2423 37779 : return ka.m_enode->m_index - kb.m_enode->m_index;
2424 : }
2425 :
2426 : /* Return a new json::object of the form
2427 : {"scc" : [per-snode-IDs]}, */
2428 :
2429 : std::unique_ptr<json::object>
2430 1 : worklist::to_json () const
2431 : {
2432 1 : auto worklist_obj = std::make_unique<json::object> ();
2433 :
2434 1 : worklist_obj->set ("scc", m_scc.to_json ());
2435 :
2436 : /* The following field isn't yet being JSONified:
2437 : queue_t m_queue; */
2438 :
2439 1 : return worklist_obj;
2440 : }
2441 :
2442 : /* exploded_graph's ctor. */
2443 :
2444 3573 : exploded_graph::exploded_graph (const supergraph &sg, logger *logger,
2445 : const extrinsic_state &ext_state,
2446 : const state_purge_map *purge_map,
2447 : const analysis_plan &plan,
2448 : int verbosity)
2449 3573 : : m_sg (sg), m_logger (logger),
2450 3573 : m_worklist (*this, plan),
2451 3573 : m_ext_state (ext_state),
2452 3573 : m_purge_map (purge_map),
2453 3573 : m_plan (plan),
2454 3573 : m_diagnostic_manager (logger, ext_state.get_engine (), verbosity),
2455 7142 : m_global_stats (m_sg.m_nodes.length ()),
2456 10715 : m_functionless_stats (m_sg.m_nodes.length ())
2457 : {
2458 7146 : m_origin = get_or_create_node
2459 3573 : (program_point::origin (*ext_state.get_model_manager ()),
2460 7146 : program_state (ext_state), nullptr);
2461 3573 : }
2462 :
2463 : /* exploded_graph's dtor. */
2464 :
2465 3573 : exploded_graph::~exploded_graph ()
2466 : {
2467 279653 : for (auto iter : m_per_point_data)
2468 552160 : delete iter.second;
2469 3924 : for (auto iter : m_per_function_data)
2470 351 : delete iter.second;
2471 18799 : for (auto iter : m_per_function_stats)
2472 11657 : delete iter.second;
2473 15127 : for (auto iter : m_per_call_string_data)
2474 11554 : delete iter.second;
2475 7146 : }
2476 :
2477 : /* Subroutine for use when implementing __attribute__((tainted_args))
2478 : on functions and on function pointer fields in structs.
2479 :
2480 : Called on STATE representing a call to FNDECL.
2481 : Mark all params of FNDECL in STATE as "tainted". Mark the value of all
2482 : regions pointed to by params of FNDECL as "tainted".
2483 :
2484 : Return true if successful; return false if the "taint" state machine
2485 : was not found. */
2486 :
2487 : static bool
2488 212 : mark_params_as_tainted (program_state *state, tree fndecl,
2489 : const extrinsic_state &ext_state)
2490 : {
2491 212 : unsigned taint_sm_idx;
2492 212 : if (!ext_state.get_sm_idx_by_name ("taint", &taint_sm_idx))
2493 : return false;
2494 212 : sm_state_map *smap = state->m_checker_states[taint_sm_idx];
2495 :
2496 212 : const state_machine &sm = ext_state.get_sm (taint_sm_idx);
2497 212 : state_machine::state_t tainted = sm.get_state_by_name ("tainted");
2498 :
2499 212 : region_model_manager *mgr = ext_state.get_model_manager ();
2500 :
2501 212 : function *fun = DECL_STRUCT_FUNCTION (fndecl);
2502 212 : gcc_assert (fun);
2503 :
2504 503 : for (tree iter_parm = DECL_ARGUMENTS (fndecl); iter_parm;
2505 291 : iter_parm = DECL_CHAIN (iter_parm))
2506 : {
2507 291 : tree param = iter_parm;
2508 291 : if (tree parm_default_ssa = ssa_default_def (fun, iter_parm))
2509 229 : param = parm_default_ssa;
2510 291 : const region *param_reg = state->m_region_model->get_lvalue (param, nullptr);
2511 291 : const svalue *init_sval = mgr->get_or_create_initial_value (param_reg);
2512 291 : smap->set_state (state->m_region_model, init_sval,
2513 : tainted, nullptr /*origin_new_sval*/, ext_state);
2514 291 : if (POINTER_TYPE_P (TREE_TYPE (param)))
2515 : {
2516 56 : const region *pointee_reg = mgr->get_symbolic_region (init_sval);
2517 : /* Mark "*param" as tainted. */
2518 56 : const svalue *init_pointee_sval
2519 56 : = mgr->get_or_create_initial_value (pointee_reg);
2520 56 : smap->set_state (state->m_region_model, init_pointee_sval,
2521 : tainted, nullptr /*origin_new_sval*/, ext_state);
2522 : }
2523 : }
2524 :
2525 : return true;
2526 : }
2527 :
2528 : /* Custom event for use by tainted_args_function_info when a function
2529 : has been marked with __attribute__((tainted_args)). */
2530 :
2531 : class tainted_args_function_custom_event : public custom_event
2532 : {
2533 : public:
2534 109 : tainted_args_function_custom_event (const event_loc_info &loc_info)
2535 : : custom_event (loc_info),
2536 109 : m_fndecl (loc_info.m_fndecl)
2537 : {
2538 : }
2539 :
2540 : void
2541 218 : print_desc (pretty_printer &pp) const final override
2542 : {
2543 218 : pp_printf (&pp,
2544 : "function %qE marked with %<__attribute__((tainted_args))%>",
2545 218 : m_fndecl);
2546 218 : }
2547 :
2548 : private:
2549 : tree m_fndecl;
2550 : };
2551 :
2552 : /* Custom exploded_edge info for top-level calls to a function
2553 : marked with __attribute__((tainted_args)). */
2554 :
2555 : class tainted_args_function_info : public custom_edge_info
2556 : {
2557 : public:
2558 202 : tainted_args_function_info (tree fndecl)
2559 202 : : m_fndecl (fndecl)
2560 : {}
2561 :
2562 0 : void print (pretty_printer *pp) const final override
2563 : {
2564 0 : pp_string (pp, "call to tainted_args function");
2565 0 : };
2566 :
2567 274 : bool update_model (region_model *model,
2568 : const exploded_edge *eedge,
2569 : region_model_context *ctxt) const final override
2570 : {
2571 274 : function *fun = eedge->m_dest->get_function ();
2572 274 : gcc_assert (fun);
2573 274 : model->push_frame (*fun, nullptr, nullptr, ctxt);
2574 274 : return true;
2575 : }
2576 :
2577 109 : void add_events_to_path (checker_path *emission_path,
2578 : const exploded_edge &,
2579 : pending_diagnostic &,
2580 : const state_transition *) const final override
2581 : {
2582 109 : emission_path->add_event
2583 109 : (std::make_unique<tainted_args_function_custom_event>
2584 109 : (event_loc_info (DECL_SOURCE_LOCATION (m_fndecl), m_fndecl, 0)));
2585 109 : }
2586 :
2587 : private:
2588 : tree m_fndecl;
2589 : };
2590 :
2591 : /* Ensure that there is an exploded_node representing an external call to
2592 : FUN, adding it to the worklist if creating it.
2593 :
2594 : Add an edge from the origin exploded_node to the function entrypoint
2595 : exploded_node.
2596 :
2597 : Return the exploded_node for the entrypoint to the function. */
2598 :
2599 : exploded_node *
2600 11815 : exploded_graph::add_function_entry (const function &fun)
2601 : {
2602 11815 : gcc_assert (gimple_has_body_p (fun.decl));
2603 :
2604 : /* Be idempotent. */
2605 11815 : function *key = const_cast<function *> (&fun);
2606 11815 : if (m_functions_with_enodes.contains (key))
2607 : {
2608 305 : logger * const logger = get_logger ();
2609 305 : if (logger)
2610 0 : logger->log ("entrypoint for %qE already exists", fun.decl);
2611 : return nullptr;
2612 : }
2613 :
2614 11510 : program_point point
2615 11510 : = program_point::from_function_entry (*m_ext_state.get_model_manager (),
2616 : m_sg, fun);
2617 11510 : program_state state (m_ext_state);
2618 11510 : state.push_frame (m_ext_state, fun);
2619 :
2620 11510 : std::unique_ptr<custom_edge_info> edge_info = nullptr;
2621 :
2622 11510 : if (lookup_attribute ("tainted_args", DECL_ATTRIBUTES (fun.decl)))
2623 : {
2624 202 : if (mark_params_as_tainted (&state, fun.decl, m_ext_state))
2625 202 : edge_info = std::make_unique<tainted_args_function_info> (fun.decl);
2626 : }
2627 :
2628 11510 : if (!state.m_valid)
2629 : return nullptr;
2630 :
2631 11510 : exploded_node *enode = get_or_create_node (point, state, nullptr);
2632 11510 : if (!enode)
2633 : return nullptr;
2634 :
2635 11502 : add_edge (m_origin, enode, nullptr, false, std::move (edge_info));
2636 :
2637 11502 : m_functions_with_enodes.add (key);
2638 :
2639 11502 : return enode;
2640 11510 : }
2641 :
2642 : /* Get or create an exploded_node for (POINT, STATE).
2643 : If a new node is created and ADD_TO_WORKLIST is true,
2644 : it is added to the worklist.
2645 :
2646 : Use ENODE_FOR_DIAG, a pre-existing enode, for any diagnostics
2647 : that need to be emitted (e.g. when purging state *before* we have
2648 : a new enode). */
2649 :
2650 : exploded_node *
2651 376761 : exploded_graph::get_or_create_node (const program_point &point,
2652 : const program_state &state,
2653 : exploded_node *enode_for_diag,
2654 : bool add_to_worklist)
2655 : {
2656 376761 : logger * const logger = get_logger ();
2657 376761 : LOG_FUNC (logger);
2658 376761 : if (logger)
2659 : {
2660 119 : format f (false);
2661 119 : pretty_printer *pp = logger->get_printer ();
2662 119 : logger->start_log_line ();
2663 119 : pp_string (pp, "point: ");
2664 119 : point.print (pp, f);
2665 119 : logger->end_log_line ();
2666 119 : state.dump_to_logger (*logger);
2667 : }
2668 :
2669 : /* Stop exploring paths for which we don't know how to effectively
2670 : model the state. */
2671 376761 : if (!state.m_valid)
2672 : {
2673 0 : if (logger)
2674 0 : logger->log ("invalid state; not creating node");
2675 : return nullptr;
2676 : }
2677 :
2678 376761 : if (point.get_call_string ().calc_recursion_depth ()
2679 376761 : > param_analyzer_max_recursion_depth)
2680 : {
2681 590 : if (logger)
2682 0 : logger->log ("rejecting node: recursion limit exceeded");
2683 : return nullptr;
2684 : }
2685 :
2686 748769 : auto_cfun sentinel (point.get_function ());
2687 :
2688 376171 : state.validate (get_ext_state ());
2689 :
2690 : //state.dump (get_ext_state ());
2691 :
2692 : /* Prune state to try to improve the chances of a cache hit,
2693 : avoiding generating redundant nodes. */
2694 376171 : uncertainty_t uncertainty;
2695 376171 : program_state pruned_state
2696 376171 : = state.prune_for_point (*this, point, enode_for_diag, &uncertainty);
2697 :
2698 376171 : pruned_state.validate (get_ext_state ());
2699 :
2700 : //pruned_state.dump (get_ext_state ());
2701 :
2702 376171 : if (logger)
2703 119 : pruned_state.dump_to_logger (*logger, "pruned_state");
2704 :
2705 748769 : stats *per_fn_stats = get_or_create_function_stats (point.get_function ());
2706 :
2707 376171 : stats *per_cs_stats
2708 376171 : = &get_or_create_per_call_string_data (point.get_call_string ())->m_stats;
2709 :
2710 376171 : point_and_state ps (point, pruned_state);
2711 376171 : ps.validate (m_ext_state);
2712 376171 : if (exploded_node **slot = m_point_and_state_to_node.get (&ps))
2713 : {
2714 : /* An exploded_node for PS already exists. */
2715 2480 : if (logger)
2716 3 : logger->log ("reused EN: %i", (*slot)->m_index);
2717 2480 : m_global_stats.m_node_reuse_count++;
2718 2480 : per_fn_stats->m_node_reuse_count++;
2719 2480 : per_cs_stats->m_node_reuse_count++;
2720 2480 : return *slot;
2721 : }
2722 :
2723 373691 : per_program_point_data *per_point_data
2724 373691 : = get_or_create_per_program_point_data (point);
2725 :
2726 : /* Consider merging state with another enode at this program_point. */
2727 891072 : if (flag_analyzer_state_merge && point.state_merge_at_p ())
2728 : {
2729 : exploded_node *existing_enode;
2730 : unsigned i;
2731 221453 : FOR_EACH_VEC_ELT (per_point_data->m_enodes, i, existing_enode)
2732 : {
2733 73952 : if (logger)
2734 23 : logger->log ("considering merging with existing EN: %i for point",
2735 23 : existing_enode->m_index);
2736 73952 : gcc_assert (existing_enode->get_point () == point);
2737 73952 : const program_state &existing_state = existing_enode->get_state ();
2738 :
2739 : /* This merges successfully within the loop. */
2740 :
2741 73952 : program_state merged_state (m_ext_state);
2742 73952 : if (pruned_state.can_merge_with_p (existing_state, m_ext_state, point,
2743 : &merged_state))
2744 : {
2745 25306 : merged_state.validate (m_ext_state);
2746 25306 : if (logger)
2747 23 : logger->log ("merging new state with that of EN: %i",
2748 23 : existing_enode->m_index);
2749 :
2750 : /* Try again for a cache hit.
2751 : Whether we get one or not, merged_state's value_ids have no
2752 : relationship to those of the input state, and thus to those
2753 : of CHANGE, so we must purge any svalue_ids from *CHANGE. */
2754 25306 : ps.set_state (std::move (merged_state));
2755 :
2756 25306 : if (exploded_node **slot = m_point_and_state_to_node.get (&ps))
2757 : {
2758 : /* An exploded_node for PS already exists. */
2759 1405 : if (logger)
2760 4 : logger->log ("reused EN: %i", (*slot)->m_index);
2761 1405 : m_global_stats.m_node_reuse_after_merge_count++;
2762 1405 : per_fn_stats->m_node_reuse_after_merge_count++;
2763 1405 : per_cs_stats->m_node_reuse_after_merge_count++;
2764 1405 : return *slot;
2765 : }
2766 : }
2767 : else
2768 48646 : if (logger)
2769 0 : logger->log ("not merging new state with that of EN: %i",
2770 0 : existing_enode->m_index);
2771 73952 : }
2772 : }
2773 :
2774 : /* Impose a limit on the number of enodes per program point, and
2775 : simply stop if we exceed it. */
2776 372286 : if ((int)per_point_data->m_enodes.length ()
2777 372286 : >= param_analyzer_max_enodes_per_program_point)
2778 : {
2779 1097 : pretty_printer pp;
2780 1097 : point.print (&pp, format (false));
2781 1097 : print_enode_indices (&pp, per_point_data->m_enodes);
2782 1097 : if (logger)
2783 0 : logger->log ("not creating enode; too many at program point: %s",
2784 : pp_formatted_text (&pp));
2785 2190 : warning_at (point.get_location (), OPT_Wanalyzer_too_complex,
2786 : "terminating analysis for this program point: %s",
2787 : pp_formatted_text (&pp));
2788 1097 : per_point_data->m_excess_enodes++;
2789 1097 : return nullptr;
2790 1097 : }
2791 :
2792 371189 : ps.validate (m_ext_state);
2793 :
2794 : /* An exploded_node for "ps" doesn't already exist; create one. */
2795 738809 : exploded_node *node = new exploded_node (std::move (ps), m_nodes.length ());
2796 371189 : add_node (node);
2797 371189 : m_point_and_state_to_node.put (node->get_ps_key (), node);
2798 :
2799 : /* Update per-program_point data. */
2800 371189 : per_point_data->m_enodes.safe_push (node);
2801 :
2802 371189 : m_global_stats.m_num_nodes++;
2803 371189 : per_fn_stats->m_num_nodes++;
2804 371189 : per_cs_stats->m_num_nodes++;
2805 :
2806 371189 : if (logger)
2807 : {
2808 112 : format f (false);
2809 112 : pretty_printer *pp = logger->get_printer ();
2810 112 : logger->log ("created EN: %i", node->m_index);
2811 112 : logger->start_log_line ();
2812 112 : pp_string (pp, "point: ");
2813 112 : point.print (pp, f);
2814 112 : logger->end_log_line ();
2815 112 : node->get_state ().dump_to_logger (*logger);
2816 : }
2817 :
2818 : /* Add the new node to the worlist. */
2819 371189 : if (add_to_worklist)
2820 363693 : m_worklist.add_node (node);
2821 : else
2822 7496 : node->set_status (exploded_node::status::special);
2823 : return node;
2824 752932 : }
2825 :
2826 : /* Add an exploded_edge from SRC to DEST, recording its association
2827 : with SEDGE (which may be NULL), and, if non-NULL, taking ownership
2828 : of CUSTOM_INFO. COULD_DO_WORK is used for detecting infinite loops.
2829 : Return the newly-created eedge. */
2830 :
2831 : exploded_edge *
2832 383640 : exploded_graph::add_edge (exploded_node *src, exploded_node *dest,
2833 : const superedge *sedge, bool could_do_work,
2834 : std::unique_ptr<custom_edge_info> custom_info)
2835 : {
2836 383640 : if (get_logger ())
2837 116 : get_logger ()->log ("creating edge EN: %i -> EN: %i",
2838 116 : src->m_index, dest->m_index);
2839 383640 : exploded_edge *e
2840 : = new exploded_edge (src, dest, sedge, could_do_work,
2841 383640 : std::move (custom_info));
2842 383640 : digraph<eg_traits>::add_edge (e);
2843 383640 : return e;
2844 : }
2845 :
2846 : /* Ensure that this graph has per-program_point-data for POINT;
2847 : borrow a pointer to it. */
2848 :
2849 : per_program_point_data *
2850 373691 : exploded_graph::
2851 : get_or_create_per_program_point_data (const program_point &point)
2852 : {
2853 373691 : if (per_program_point_data **slot = m_per_point_data.get (&point))
2854 97611 : return *slot;
2855 :
2856 276080 : per_program_point_data *per_point_data = new per_program_point_data (point);
2857 276080 : m_per_point_data.put (&per_point_data->m_key, per_point_data);
2858 276080 : return per_point_data;
2859 : }
2860 :
2861 : /* Get this graph's per-program-point-data for POINT if there is any,
2862 : otherwise nullptr. */
2863 :
2864 : per_program_point_data *
2865 0 : exploded_graph::get_per_program_point_data (const program_point &point) const
2866 : {
2867 0 : if (per_program_point_data **slot
2868 0 : = const_cast <point_map_t &> (m_per_point_data).get (&point))
2869 0 : return *slot;
2870 :
2871 : return nullptr;
2872 : }
2873 :
2874 : /* Ensure that this graph has per-call_string-data for CS;
2875 : borrow a pointer to it. */
2876 :
2877 : per_call_string_data *
2878 376171 : exploded_graph::get_or_create_per_call_string_data (const call_string &cs)
2879 : {
2880 376171 : if (per_call_string_data **slot = m_per_call_string_data.get (&cs))
2881 364617 : return *slot;
2882 :
2883 23104 : per_call_string_data *data = new per_call_string_data (cs, m_sg.m_nodes.length ());
2884 11554 : m_per_call_string_data.put (&data->m_key,
2885 : data);
2886 11554 : return data;
2887 : }
2888 :
2889 : /* Ensure that this graph has per-function-data for FUN;
2890 : borrow a pointer to it. */
2891 :
2892 : per_function_data *
2893 442 : exploded_graph::get_or_create_per_function_data (function *fun)
2894 : {
2895 442 : if (per_function_data **slot = m_per_function_data.get (fun))
2896 91 : return *slot;
2897 :
2898 351 : per_function_data *data = new per_function_data ();
2899 351 : m_per_function_data.put (fun, data);
2900 351 : return data;
2901 : }
2902 :
2903 : /* Get this graph's per-function-data for FUN if there is any,
2904 : otherwise nullptr. */
2905 :
2906 : per_function_data *
2907 541 : exploded_graph::get_per_function_data (function *fun) const
2908 : {
2909 1082 : if (per_function_data **slot
2910 541 : = const_cast <per_function_data_t &> (m_per_function_data).get (fun))
2911 452 : return *slot;
2912 :
2913 : return nullptr;
2914 : }
2915 :
2916 : /* Return true if FUN should be traversed directly, rather than only as
2917 : called via other functions. */
2918 :
2919 : static bool
2920 11661 : toplevel_function_p (const function &fun, logger *logger)
2921 : {
2922 : /* Don't directly traverse into functions that have an "__analyzer_"
2923 : prefix. Doing so is useful for the analyzer test suite, allowing
2924 : us to have functions that are called in traversals, but not directly
2925 : explored, thus testing how the analyzer handles calls and returns.
2926 : With this, we can have DejaGnu directives that cover just the case
2927 : of where a function is called by another function, without generating
2928 : excess messages from the case of the first function being traversed
2929 : directly. */
2930 : #define ANALYZER_PREFIX "__analyzer_"
2931 11661 : if (!strncmp (IDENTIFIER_POINTER (DECL_NAME (fun.decl)), ANALYZER_PREFIX,
2932 : strlen (ANALYZER_PREFIX)))
2933 : {
2934 151 : if (logger)
2935 0 : logger->log ("not traversing %qE (starts with %qs)",
2936 : fun.decl, ANALYZER_PREFIX);
2937 : return false;
2938 : }
2939 :
2940 11510 : if (logger)
2941 6 : logger->log ("traversing %qE (all checks passed)", fun.decl);
2942 :
2943 : return true;
2944 : }
2945 :
2946 : /* Custom event for use by tainted_call_info when a callback field has been
2947 : marked with __attribute__((tainted_args)), for labelling the field. */
2948 :
2949 : class tainted_args_field_custom_event : public custom_event
2950 : {
2951 : public:
2952 4 : tainted_args_field_custom_event (tree field)
2953 4 : : custom_event (event_loc_info (DECL_SOURCE_LOCATION (field), NULL_TREE, 0)),
2954 4 : m_field (field)
2955 : {
2956 4 : }
2957 :
2958 8 : void print_desc (pretty_printer &pp) const final override
2959 : {
2960 8 : pp_printf (&pp,
2961 : "field %qE of %qT"
2962 : " is marked with %<__attribute__((tainted_args))%>",
2963 8 : m_field, DECL_CONTEXT (m_field));
2964 8 : }
2965 :
2966 : private:
2967 : tree m_field;
2968 : };
2969 :
2970 : /* Custom event for use by tainted_call_info when a callback field has been
2971 : marked with __attribute__((tainted_args)), for labelling the function used
2972 : in that callback. */
2973 :
2974 : class tainted_args_callback_custom_event : public custom_event
2975 : {
2976 : public:
2977 4 : tainted_args_callback_custom_event (const event_loc_info &loc_info,
2978 : tree field)
2979 : : custom_event (loc_info),
2980 4 : m_field (field)
2981 : {
2982 : }
2983 :
2984 8 : void print_desc (pretty_printer &pp) const final override
2985 : {
2986 8 : pp_printf (&pp,
2987 : "function %qE used as initializer for field %qE"
2988 : " marked with %<__attribute__((tainted_args))%>",
2989 8 : get_fndecl (), m_field);
2990 8 : }
2991 :
2992 : private:
2993 : tree m_field;
2994 : };
2995 :
2996 : /* Custom edge info for use when adding a function used by a callback field
2997 : marked with '__attribute__((tainted_args))'. */
2998 :
2999 : class tainted_args_call_info : public custom_edge_info
3000 : {
3001 : public:
3002 10 : tainted_args_call_info (tree field, tree fndecl, location_t loc)
3003 10 : : m_field (field), m_fndecl (fndecl), m_loc (loc)
3004 : {}
3005 :
3006 0 : void print (pretty_printer *pp) const final override
3007 : {
3008 0 : pp_string (pp, "call to tainted field");
3009 0 : };
3010 :
3011 13 : bool update_model (region_model *model,
3012 : const exploded_edge *eedge,
3013 : region_model_context *) const final override
3014 : {
3015 26 : model->push_frame (*eedge->m_dest->get_function (),
3016 : nullptr, nullptr, nullptr);
3017 13 : return true;
3018 : }
3019 :
3020 4 : void add_events_to_path (checker_path *emission_path,
3021 : const exploded_edge &,
3022 : pending_diagnostic &,
3023 : const state_transition *) const final override
3024 : {
3025 : /* Show the field in the struct declaration, e.g.
3026 : "(1) field 'store' is marked with '__attribute__((tainted_args))'" */
3027 4 : emission_path->add_event
3028 4 : (std::make_unique<tainted_args_field_custom_event> (m_field));
3029 :
3030 : /* Show the callback in the initializer
3031 : e.g.
3032 : "(2) function 'gadget_dev_desc_UDC_store' used as initializer
3033 : for field 'store' marked with '__attribute__((tainted_args))'". */
3034 4 : emission_path->add_event
3035 4 : (std::make_unique<tainted_args_callback_custom_event>
3036 4 : (event_loc_info (m_loc, m_fndecl, 0),
3037 : m_field));
3038 4 : }
3039 :
3040 : private:
3041 : tree m_field;
3042 : tree m_fndecl;
3043 : location_t m_loc;
3044 : };
3045 :
3046 : /* Given an initializer at LOC for FIELD marked with
3047 : '__attribute__((tainted_args))' initialized with FNDECL, add an
3048 : entrypoint to FNDECL to EG (and to its worklist) where the params to
3049 : FNDECL are marked as tainted. */
3050 :
3051 : static void
3052 10 : add_tainted_args_callback (exploded_graph *eg, tree field, tree fndecl,
3053 : location_t loc)
3054 : {
3055 10 : logger *logger = eg->get_logger ();
3056 :
3057 10 : LOG_SCOPE (logger);
3058 :
3059 10 : if (!gimple_has_body_p (fndecl))
3060 : return;
3061 :
3062 10 : const extrinsic_state &ext_state = eg->get_ext_state ();
3063 :
3064 10 : function *fun = DECL_STRUCT_FUNCTION (fndecl);
3065 10 : gcc_assert (fun);
3066 :
3067 10 : program_point point
3068 10 : = program_point::from_function_entry (*ext_state.get_model_manager (),
3069 : eg->get_supergraph (), *fun);
3070 10 : program_state state (ext_state);
3071 10 : state.push_frame (ext_state, *fun);
3072 :
3073 10 : if (!mark_params_as_tainted (&state, fndecl, ext_state))
3074 : return;
3075 :
3076 10 : if (!state.m_valid)
3077 : return;
3078 :
3079 10 : exploded_node *enode = eg->get_or_create_node (point, state, nullptr);
3080 10 : if (logger)
3081 : {
3082 0 : if (enode)
3083 0 : logger->log ("created EN %i for tainted_args %qE entrypoint",
3084 0 : enode->m_index, fndecl);
3085 : else
3086 : {
3087 0 : logger->log ("did not create enode for tainted_args %qE entrypoint",
3088 : fndecl);
3089 0 : return;
3090 : }
3091 : }
3092 :
3093 10 : eg->add_edge (eg->get_origin (), enode, nullptr, false,
3094 10 : std::make_unique<tainted_args_call_info> (field, fndecl, loc));
3095 10 : }
3096 :
3097 : /* Callback for walk_tree for finding callbacks within initializers;
3098 : ensure that any callback initializer where the corresponding field is
3099 : marked with '__attribute__((tainted_args))' is treated as an entrypoint
3100 : to the analysis, special-casing that the inputs to the callback are
3101 : untrustworthy. */
3102 :
3103 : static tree
3104 33296 : add_any_callbacks (tree *tp, int *, void *data)
3105 : {
3106 33296 : exploded_graph *eg = (exploded_graph *)data;
3107 33296 : if (TREE_CODE (*tp) == CONSTRUCTOR)
3108 : {
3109 : /* Find fields with the "tainted_args" attribute.
3110 : walk_tree only walks the values, not the index values;
3111 : look at the index values. */
3112 : unsigned HOST_WIDE_INT idx;
3113 : constructor_elt *ce;
3114 :
3115 21815 : for (idx = 0; vec_safe_iterate (CONSTRUCTOR_ELTS (*tp), idx, &ce);
3116 : idx++)
3117 16264 : if (ce->index && TREE_CODE (ce->index) == FIELD_DECL)
3118 13935 : if (lookup_attribute ("tainted_args", DECL_ATTRIBUTES (ce->index)))
3119 : {
3120 10 : tree value = ce->value;
3121 10 : if (TREE_CODE (value) == ADDR_EXPR
3122 10 : && TREE_CODE (TREE_OPERAND (value, 0)) == FUNCTION_DECL)
3123 20 : add_tainted_args_callback (eg, ce->index,
3124 10 : TREE_OPERAND (value, 0),
3125 10 : EXPR_LOCATION (value));
3126 : }
3127 : }
3128 :
3129 33296 : return NULL_TREE;
3130 : }
3131 :
3132 : /* Add initial nodes to EG, with entrypoints for externally-callable
3133 : functions. */
3134 :
3135 : void
3136 3573 : exploded_graph::build_initial_worklist ()
3137 : {
3138 3573 : logger * const logger = get_logger ();
3139 3573 : LOG_SCOPE (logger);
3140 :
3141 3573 : cgraph_node *node;
3142 15234 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
3143 : {
3144 11661 : function *fun = node->get_fun ();
3145 11661 : gcc_assert (fun);
3146 11661 : if (!toplevel_function_p (*fun, logger))
3147 151 : continue;
3148 11510 : exploded_node *enode = add_function_entry (*fun);
3149 11510 : if (logger)
3150 : {
3151 6 : if (enode)
3152 6 : logger->log ("created EN %i for %qE entrypoint",
3153 6 : enode->m_index, fun->decl);
3154 : else
3155 0 : logger->log ("did not create enode for %qE entrypoint", fun->decl);
3156 : }
3157 : }
3158 :
3159 : /* Find callbacks that are reachable from global initializers. */
3160 3573 : varpool_node *vpnode;
3161 10325 : FOR_EACH_VARIABLE (vpnode)
3162 : {
3163 6752 : tree decl = vpnode->decl;
3164 6752 : tree init = DECL_INITIAL (decl);
3165 6752 : if (!init)
3166 1387 : continue;
3167 5365 : walk_tree (&init, add_any_callbacks, this, nullptr);
3168 : }
3169 3573 : }
3170 :
3171 : /* The main loop of the analysis.
3172 : Take freshly-created exploded_nodes from the worklist, calling
3173 : process_node on them to explore the <point, state> graph.
3174 : Add edges to their successors, potentially creating new successors
3175 : (which are also added to the worklist). */
3176 :
3177 : void
3178 3573 : exploded_graph::process_worklist ()
3179 : {
3180 3573 : logger * const logger = get_logger ();
3181 3573 : LOG_SCOPE (logger);
3182 3573 : auto_timevar tv (TV_ANALYZER_WORKLIST);
3183 :
3184 353560 : while (m_worklist.length () > 0)
3185 : {
3186 346479 : exploded_node *node = m_worklist.take_next ();
3187 346479 : gcc_assert (node->get_status () == exploded_node::status::worklist);
3188 :
3189 346479 : if (logger)
3190 110 : logger->log ("next to process: EN: %i", node->m_index);
3191 :
3192 : /* If we have a run of nodes at the same point, try merging and
3193 : processing them together, rather than pairwise or individually. */
3194 346479 : if (flag_analyzer_state_merge
3195 346479 : && node->get_point ().state_merge_at_p ())
3196 131072 : if (maybe_process_run_of_enodes (node))
3197 6972 : goto handle_limit;
3198 :
3199 : /* Avoid exponential explosions of nodes by attempting to merge
3200 : nodes that are at the same program point and which have
3201 : sufficiently similar state. */
3202 339507 : if (flag_analyzer_state_merge && node != m_origin)
3203 332330 : if (exploded_node *node_2 = m_worklist.peek_next ())
3204 : {
3205 281411 : gcc_assert (node_2->get_status ()
3206 : == exploded_node::status::worklist);
3207 281411 : gcc_assert (node != node_2);
3208 :
3209 281411 : if (logger)
3210 57 : logger->log ("peek worklist: EN: %i", node_2->m_index);
3211 :
3212 281411 : if (node->get_point () == node_2->get_point ())
3213 : {
3214 28609 : const program_point &point = node->get_point ();
3215 28609 : if (logger)
3216 : {
3217 2 : format f (false);
3218 2 : pretty_printer *pp = logger->get_printer ();
3219 2 : logger->start_log_line ();
3220 2 : logger->log_partial
3221 2 : ("got potential merge EN: %i and EN: %i at ",
3222 2 : node->m_index, node_2->m_index);
3223 2 : point.print (pp, f);
3224 2 : logger->end_log_line ();
3225 : }
3226 28609 : const program_state &state = node->get_state ();
3227 28609 : const program_state &state_2 = node_2->get_state ();
3228 :
3229 : /* They shouldn't be equal, or we wouldn't have two
3230 : separate nodes. */
3231 28609 : gcc_assert (state != state_2);
3232 :
3233 28609 : program_state merged_state (m_ext_state);
3234 28609 : if (state.can_merge_with_p (state_2, m_ext_state,
3235 : point, &merged_state))
3236 : {
3237 2722 : if (logger)
3238 2 : logger->log ("merging EN: %i and EN: %i",
3239 2 : node->m_index, node_2->m_index);
3240 :
3241 2722 : if (merged_state == state)
3242 : {
3243 : /* Then merge node_2 into node by adding an edge. */
3244 376 : add_edge (node_2, node, nullptr, false);
3245 :
3246 : /* Remove node_2 from the worklist. */
3247 376 : m_worklist.take_next ();
3248 376 : node_2->set_status (exploded_node::status::merger);
3249 :
3250 : /* Continue processing "node" below. */
3251 : }
3252 2346 : else if (merged_state == state_2)
3253 : {
3254 : /* Then merge node into node_2, and leave node_2
3255 : in the worklist, to be processed on the next
3256 : iteration. */
3257 1367 : add_edge (node, node_2, nullptr, false);
3258 1367 : node->set_status (exploded_node::status::merger);
3259 1367 : continue;
3260 : }
3261 : else
3262 : {
3263 : /* We have a merged state that differs from
3264 : both state and state_2. */
3265 :
3266 : /* Remove node_2 from the worklist. */
3267 979 : m_worklist.take_next ();
3268 :
3269 : /* Create (or get) an exploded node for the merged
3270 : states, adding to the worklist. */
3271 979 : exploded_node *merged_enode
3272 979 : = get_or_create_node (node->get_point (),
3273 : merged_state, node);
3274 979 : if (merged_enode == nullptr)
3275 36 : continue;
3276 :
3277 943 : if (logger)
3278 2 : logger->log ("merged EN: %i and EN: %i into EN: %i",
3279 2 : node->m_index, node_2->m_index,
3280 2 : merged_enode->m_index);
3281 :
3282 : /* "node" and "node_2" have both now been removed
3283 : from the worklist; we should not process them.
3284 :
3285 : "merged_enode" may be a new node; if so it will be
3286 : processed in a subsequent iteration.
3287 : Alternatively, "merged_enode" could be an existing
3288 : node; one way the latter can
3289 : happen is if we end up merging a succession of
3290 : similar nodes into one. */
3291 :
3292 : /* If merged_node is one of the two we were merging,
3293 : add it back to the worklist to ensure it gets
3294 : processed.
3295 :
3296 : Add edges from the merged nodes to it (but not a
3297 : self-edge). */
3298 943 : if (merged_enode == node)
3299 1 : m_worklist.add_node (merged_enode);
3300 : else
3301 : {
3302 942 : add_edge (node, merged_enode, nullptr, false);
3303 942 : node->set_status (exploded_node::status::merger);
3304 : }
3305 :
3306 943 : if (merged_enode == node_2)
3307 5 : m_worklist.add_node (merged_enode);
3308 : else
3309 : {
3310 938 : add_edge (node_2, merged_enode, nullptr, false);
3311 938 : node_2->set_status (exploded_node::status::merger);
3312 : }
3313 :
3314 943 : continue;
3315 943 : }
3316 : }
3317 :
3318 : /* TODO: should we attempt more than two nodes,
3319 : or just do pairs of nodes? (and hope that we get
3320 : a cascade of mergers). */
3321 28609 : }
3322 : }
3323 :
3324 337161 : process_node (node);
3325 :
3326 344133 : handle_limit:
3327 : /* Impose a hard limit on the number of exploded nodes, to ensure
3328 : that the analysis terminates in the face of pathological state
3329 : explosion (or bugs). */
3330 344133 : const int limit
3331 : = (// Per-supernode limit:
3332 344133 : (m_sg.num_nodes () * param_analyzer_supernode_explosion_factor)
3333 : // Allow one for the "origin" enode:
3334 344133 : + 1);
3335 344133 : if (m_global_stats.m_num_nodes > limit)
3336 : {
3337 65 : if (logger)
3338 0 : logger->log ("bailing out; too many nodes");
3339 195 : warning_at (node->get_point ().get_location (),
3340 65 : OPT_Wanalyzer_too_complex,
3341 : "analysis bailed out early"
3342 : " (%i enodes for %i snodes)",
3343 : m_nodes.length (),
3344 65 : m_sg.num_nodes ());
3345 65 : return;
3346 : }
3347 : }
3348 3573 : }
3349 :
3350 : /* Attempt to process a consecutive run of sufficiently-similar nodes in
3351 : the worklist at a point flagged with state_merge_at_p (having already
3352 : popped ENODE from the head of the worklist).
3353 :
3354 : If we have a consecutive run of enodes in the worklist all of which have
3355 : a single out-edge where all these out-edges are supports_bulk_merge_p and
3356 : all have the same successor snode and call string, then
3357 : process them all together, setting their status to status::bulk_merged,
3358 : and return true.
3359 : Otherwise, return false, in which case ENODE must be processed in the
3360 : normal way.
3361 :
3362 : When processing them all together, generate successor states based
3363 : on the edge op update_state_for_bulk_merger, and then attempt to merge
3364 : these states into a minimal set of merged successor states, partitioning
3365 : the inputs by merged successor state.
3366 :
3367 : Create new exploded nodes for all of the merged states, and add edges
3368 : connecting the input enodes to the corresponding merger exploded nodes.
3369 :
3370 : We hope we have a much smaller number of merged successor states
3371 : compared to the number of input enodes - ideally just one,
3372 : if all successor states can be merged.
3373 :
3374 : Processing and merging many together as one operation rather than as
3375 : pairs avoids scaling issues where per-pair mergers could bloat the
3376 : graph with merger nodes (especially so after switch statements). */
3377 :
3378 : bool
3379 131072 : exploded_graph::
3380 : maybe_process_run_of_enodes (exploded_node *enode)
3381 : {
3382 : /* A struct for tracking per-input state. */
3383 21916 : struct item
3384 : {
3385 21916 : item (exploded_node *input_enode)
3386 21916 : : m_input_enode (input_enode),
3387 21916 : m_processed_state (input_enode->get_state ()),
3388 21916 : m_merger_idx (-1)
3389 : {}
3390 :
3391 : exploded_node *m_input_enode;
3392 : program_state m_processed_state;
3393 : int m_merger_idx;
3394 : };
3395 :
3396 131072 : gcc_assert (enode->get_status () == exploded_node::status::worklist);
3397 :
3398 131072 : const program_point &src_point = enode->get_point ();
3399 131072 : const supernode *src_snode = src_point.get_supernode ();
3400 :
3401 131072 : logger * const logger = get_logger ();
3402 131072 : LOG_SCOPE (logger);
3403 :
3404 131072 : if (src_snode->m_succs.length () != 1)
3405 : return false;
3406 :
3407 103974 : auto sedge = src_snode->m_succs[0];
3408 :
3409 103974 : if (!sedge->supports_bulk_merge_p ())
3410 : return false;
3411 :
3412 40132 : const supernode *dst_snode = src_snode->m_succs[0]->m_dest;
3413 :
3414 : /* Find a run of enodes in the worklist that all have single out-sedges
3415 : go to the same supernode, all of which are bulk-mergeable (i.e. have
3416 : a simple single intraprocedural outcome). */
3417 40132 : auto_vec <exploded_node *> enodes;
3418 40132 : enodes.safe_push (enode);
3419 55076 : while (exploded_node *enode_2 = m_worklist.peek_next ())
3420 : {
3421 49021 : gcc_assert (enode_2->get_status ()
3422 : == exploded_node::status::worklist);
3423 49021 : gcc_assert (enode_2->m_succs.length () == 0);
3424 :
3425 49021 : const program_point &point_2 = enode_2->get_point ();
3426 49021 : const supernode *src_snode_2 = point_2.get_supernode ();
3427 :
3428 49021 : if (src_snode_2->m_succs.length () != 1)
3429 : break;
3430 48207 : auto sedge_2 = src_snode_2->m_succs[0];
3431 48207 : if (sedge_2->m_dest != dst_snode)
3432 : break;
3433 16521 : if (&point_2.get_call_string () != &src_point.get_call_string ())
3434 : break;
3435 14944 : if (!sedge_2->supports_bulk_merge_p ())
3436 : break;
3437 :
3438 14944 : enodes.safe_push (enode_2);
3439 14944 : m_worklist.take_next ();
3440 14944 : }
3441 :
3442 : /* If the only node is ENODE, then give up. */
3443 40132 : if (enodes.length () == 1)
3444 : return false;
3445 :
3446 6972 : if (logger)
3447 1 : logger->log ("got run of %i bulk-mergeable enodes going to SN: %i",
3448 1 : enodes.length (), dst_snode->m_id);
3449 :
3450 : /* All of these enodes have a shared intraprocedural successor point
3451 : (even if they were for different in-edges). */
3452 6972 : program_point next_point (sedge->m_dest,
3453 6972 : src_point.get_call_string ());
3454 :
3455 : /* Calculate the successor state for each enode in enodes. */
3456 13944 : auto_delete_vec<item> items (enodes.length ());
3457 6972 : unsigned i;
3458 6972 : exploded_node *iter_enode;
3459 35860 : FOR_EACH_VEC_ELT (enodes, i, iter_enode)
3460 : {
3461 21916 : item *it = new item (iter_enode);
3462 21916 : items.quick_push (it);
3463 21916 : const program_state &state = iter_enode->get_state ();
3464 21916 : program_state *next_state = &it->m_processed_state;
3465 21916 : next_state->validate (m_ext_state);
3466 21916 : gcc_assert (iter_enode->get_supernode ()->m_succs.length () == 1);
3467 21916 : const superedge *iter_sedge = iter_enode->get_supernode ()->m_succs[0];
3468 21916 : if (auto op = iter_sedge->get_op ())
3469 196 : op->update_state_for_bulk_merger (state, *next_state);
3470 21916 : next_state->validate (m_ext_state);
3471 : }
3472 :
3473 : /* Attempt to partition the items into a set of merged states.
3474 : We hope we have a much smaller number of merged states
3475 : compared to the number of input enodes - ideally just one,
3476 : if all can be merged. */
3477 6972 : auto_delete_vec <program_state> merged_states;
3478 6972 : auto_vec<item *> first_item_for_each_merged_state;
3479 6972 : item *it;
3480 35860 : FOR_EACH_VEC_ELT (items, i, it)
3481 : {
3482 21916 : const program_state &it_state = it->m_processed_state;
3483 21916 : program_state *merged_state;
3484 21916 : unsigned iter_merger_idx;
3485 33705 : FOR_EACH_VEC_ELT (merged_states, iter_merger_idx, merged_state)
3486 : {
3487 21253 : merged_state->validate (m_ext_state);
3488 21253 : program_state merge (m_ext_state);
3489 21253 : if (it_state.can_merge_with_p (*merged_state, m_ext_state,
3490 : next_point, &merge))
3491 : {
3492 9464 : *merged_state = merge;
3493 9464 : merged_state->validate (m_ext_state);
3494 9464 : it->m_merger_idx = iter_merger_idx;
3495 9464 : if (logger)
3496 1 : logger->log ("reusing merger state %i for item %i (EN: %i)",
3497 1 : it->m_merger_idx, i, it->m_input_enode->m_index);
3498 9464 : goto got_merger;
3499 : }
3500 21253 : }
3501 : /* If it couldn't be merged with any existing merged_states,
3502 : create a new one. */
3503 12452 : if (it->m_merger_idx == -1)
3504 : {
3505 12452 : it->m_merger_idx = merged_states.length ();
3506 12452 : merged_states.safe_push (new program_state (it_state));
3507 12452 : first_item_for_each_merged_state.safe_push (it);
3508 12452 : if (logger)
3509 1 : logger->log ("using new merger state %i for item %i (EN: %i)",
3510 1 : it->m_merger_idx, i, it->m_input_enode->m_index);
3511 : }
3512 0 : got_merger:
3513 21916 : gcc_assert (it->m_merger_idx >= 0);
3514 21916 : gcc_assert ((unsigned)it->m_merger_idx < merged_states.length ());
3515 : }
3516 :
3517 : /* Create merger nodes. */
3518 20916 : auto_vec<exploded_node *> next_enodes (merged_states.length ());
3519 6972 : program_state *merged_state;
3520 26396 : FOR_EACH_VEC_ELT (merged_states, i, merged_state)
3521 : {
3522 12452 : exploded_node *src_enode
3523 12452 : = first_item_for_each_merged_state[i]->m_input_enode;
3524 12452 : exploded_node *next
3525 12452 : = get_or_create_node (next_point, *merged_state, src_enode);
3526 : /* "next" could be nullptr; we handle that when adding the edges below. */
3527 12452 : next_enodes.quick_push (next);
3528 12452 : if (logger)
3529 : {
3530 1 : if (next)
3531 1 : logger->log ("using EN: %i for merger state %i", next->m_index, i);
3532 : else
3533 0 : logger->log ("using NULL enode for merger state %i", i);
3534 : }
3535 : }
3536 :
3537 : /* Create edges from each input enode to the appropriate successor enode.
3538 : Update the status of the now-processed input enodes. */
3539 35860 : FOR_EACH_VEC_ELT (items, i, it)
3540 : {
3541 21916 : exploded_node *next = next_enodes[it->m_merger_idx];
3542 21916 : if (next)
3543 : {
3544 21623 : gcc_assert (it->m_input_enode->get_supernode ()->m_succs.length ()
3545 : == 1);
3546 21623 : const superedge *sedge
3547 21623 : = it->m_input_enode->get_supernode ()->m_succs[0];
3548 21623 : add_edge (it->m_input_enode, next, sedge,
3549 : false); /* no "work" is done during merger. */
3550 : }
3551 21916 : it->m_input_enode->set_status (exploded_node::status::bulk_merged);
3552 : }
3553 :
3554 6972 : if (logger)
3555 2 : logger->log ("merged %i in-enodes into %i out-enode(s) at SN: %i",
3556 1 : items.length (), merged_states.length (), dst_snode->m_id);
3557 :
3558 6972 : return true;
3559 138044 : }
3560 :
3561 : /* The core of exploded_graph::process_worklist (the main analysis loop),
3562 : handling one node in the worklist.
3563 :
3564 : Get successor <point, state> pairs for NODE, calling get_or_create on
3565 : them, and adding an exploded_edge to each successors.
3566 :
3567 : Freshly-created nodes will be added to the worklist. */
3568 :
3569 : void
3570 337161 : exploded_graph::process_node (exploded_node *node)
3571 : {
3572 337161 : logger * const logger = get_logger ();
3573 337161 : LOG_FUNC_1 (logger, "EN: %i", node->m_index);
3574 :
3575 337161 : node->set_status (exploded_node::status::processed);
3576 :
3577 337161 : const program_point &point = node->get_point ();
3578 :
3579 : /* Update cfun and input_location in case of an ICE: make it easier to
3580 : track down which source construct we're failing to handle. */
3581 670753 : auto_cfun sentinel (node->get_function ());
3582 :
3583 337161 : input_location = node->get_location ();
3584 :
3585 337161 : const program_state &state = node->get_state ();
3586 337161 : if (logger)
3587 : {
3588 107 : pretty_printer *pp = logger->get_printer ();
3589 107 : logger->start_log_line ();
3590 107 : pp_string (pp, "point: ");
3591 107 : point.print (pp, format (false));
3592 107 : logger->end_log_line ();
3593 107 : state.dump_to_logger (*logger);
3594 : }
3595 :
3596 : /* Don't do anything for the origin enode; the initial population of the
3597 : worklist has already added successor enodes. */
3598 337161 : if (point.get_supernode () == nullptr)
3599 : return;
3600 :
3601 : /* Specialcase for EXIT BBs, which don't have out-edges. */
3602 333592 : if (point.get_supernode ()->exit_p ())
3603 : {
3604 20364 : gcc_assert (point.get_supernode ()->m_succs.length () == 0);
3605 :
3606 20364 : if (point.get_stack_depth () > 1)
3607 : {
3608 : /* Interprocedural return. */
3609 8193 : auto &src_call_string = point.get_call_string ();
3610 :
3611 8193 : const call_string::element_t &top_of_stack
3612 8193 : = src_call_string.get_top_of_stack ();
3613 8193 : const call_string *dst_call_string = src_call_string.get_parent ();
3614 8193 : const program_point dst_point
3615 : (top_of_stack.get_return_snode_in_caller (),
3616 8193 : *dst_call_string);
3617 8193 : auto edge_info
3618 8193 : = std::make_unique<interprocedural_return> (top_of_stack.get_call_stmt ());
3619 :
3620 8193 : const program_state &src_state (node->get_state ());
3621 8193 : program_state dst_state (src_state);
3622 8193 : uncertainty_t uncertainty;
3623 8193 : impl_region_model_context ctxt (*this, node,
3624 : &src_state, &dst_state, &uncertainty,
3625 : nullptr,
3626 8193 : nullptr);
3627 8193 : edge_info->update_state (&dst_state, nullptr, &ctxt);
3628 :
3629 8193 : program_state::detect_leaks (src_state, dst_state,
3630 : nullptr, get_ext_state (),
3631 : &ctxt);
3632 :
3633 16386 : if (exploded_node *next
3634 8193 : = get_or_create_node (dst_point, dst_state, node))
3635 8109 : add_edge (node, next, nullptr, false,
3636 8109 : std::move (edge_info));
3637 16386 : }
3638 : else
3639 : {
3640 : /* End of top-level of analysis for this function.
3641 : Detect leaks, and potentially create a function summary. */
3642 12171 : node->detect_leaks (*this);
3643 :
3644 12171 : if (flag_analyzer_call_summaries
3645 24375 : && point.get_call_string ().empty_p ())
3646 : {
3647 : /* TODO: create function summary
3648 : There can be more than one; each corresponds to a different
3649 : final enode in the function. */
3650 442 : if (logger)
3651 : {
3652 0 : pretty_printer *pp = logger->get_printer ();
3653 0 : logger->log
3654 0 : ("would create function summary for %qE; state: ",
3655 : point.get_fndecl ());
3656 0 : state.dump_to_logger (*logger);
3657 : }
3658 442 : per_function_data *per_fn_data
3659 442 : = get_or_create_per_function_data (point.get_function ());
3660 442 : per_fn_data->add_call_summary (node);
3661 : }
3662 : }
3663 :
3664 : return;
3665 : }
3666 :
3667 : /* Traverse into successors of the supernode. */
3668 : int i;
3669 : superedge *succ;
3670 964168 : FOR_EACH_VEC_ELT (point.get_supernode ()->m_succs, i, succ)
3671 : {
3672 338749 : if (logger)
3673 : {
3674 107 : label_text succ_desc (succ->get_description (false));
3675 107 : logger->log ("considering SN: %i -> SN: %i (%s)",
3676 107 : succ->m_src->m_id, succ->m_dest->m_id,
3677 : succ_desc.get ());
3678 107 : }
3679 :
3680 338749 : program_point next_point (succ->m_dest, point.get_call_string ());
3681 338749 : program_state next_state (state);
3682 338749 : uncertainty_t uncertainty;
3683 :
3684 : /* Find the outcome(s) of any operation on the edge. */
3685 338749 : operation_context op_ctxt (*this, *node, *succ);
3686 :
3687 : /* Skip EH edges. */
3688 338749 : if (auto cfg_edge = succ->get_any_cfg_edge ())
3689 116265 : if (cfg_edge->flags & EDGE_EH)
3690 900 : continue;
3691 :
3692 337849 : if (auto op = succ->get_op ())
3693 272710 : op->execute (op_ctxt);
3694 : else
3695 : {
3696 : /* No-op.
3697 : Unconditional goto to the dst point, which
3698 : must be in same function.
3699 : The supernode changes, but the callstring and
3700 : state do not change. */
3701 65139 : if (logger)
3702 29 : logger->log ("handling no-op edge");
3703 65139 : auto dst_point (op_ctxt.get_next_intraprocedural_point ());
3704 65139 : if (exploded_node *next
3705 65139 : = get_or_create_node (dst_point,
3706 : node->get_state (),
3707 : node))
3708 65093 : add_edge (node, next, succ, false);
3709 : }
3710 338749 : }
3711 337161 : }
3712 :
3713 : /* Ensure that this graph has a stats instance for FN, return it.
3714 : FN can be nullptr, in which case a stats instances is returned covering
3715 : "functionless" parts of the graph (the origin node). */
3716 :
3717 : stats *
3718 376171 : exploded_graph::get_or_create_function_stats (function *fn)
3719 : {
3720 376171 : if (!fn)
3721 3573 : return &m_functionless_stats;
3722 :
3723 372598 : if (stats **slot = m_per_function_stats.get (fn))
3724 360941 : return *slot;
3725 : else
3726 : {
3727 11657 : int num_supernodes = 0;
3728 1967858 : for (auto snode : m_sg.m_nodes)
3729 1932887 : if (snode->get_function () == fn)
3730 201407 : ++num_supernodes;
3731 11657 : stats *new_stats = new stats (num_supernodes);
3732 11657 : m_per_function_stats.put (fn, new_stats);
3733 11657 : return new_stats;
3734 : }
3735 : }
3736 :
3737 : /* Print bar charts to PP showing:
3738 : - the number of enodes per function, and
3739 : - for each function:
3740 : - the number of enodes per supernode/BB
3741 : - the number of excess enodes per supernode/BB beyond the
3742 : per-program-point limit, if there were any. */
3743 :
3744 : void
3745 5 : exploded_graph::print_bar_charts (pretty_printer *pp) const
3746 : {
3747 5 : cgraph_node *cgnode;
3748 :
3749 5 : pp_string (pp, "enodes per function:");
3750 5 : pp_newline (pp);
3751 5 : bar_chart enodes_per_function;
3752 11 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode)
3753 : {
3754 6 : function *fn = cgnode->get_fun ();
3755 6 : const stats * const *s_ptr
3756 6 : = const_cast <function_stat_map_t &> (m_per_function_stats).get (fn);
3757 12 : enodes_per_function.add_item (function_name (fn),
3758 6 : s_ptr ? (*s_ptr)->get_total_enodes () : 0);
3759 : }
3760 5 : enodes_per_function.print (pp);
3761 :
3762 : /* Accumulate number of enodes per supernode. */
3763 10 : auto_vec<unsigned> enodes_per_supernode (m_sg.m_nodes.length ());
3764 175 : for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
3765 80 : enodes_per_supernode.quick_push (0);
3766 : int i;
3767 : exploded_node *enode;
3768 117 : FOR_EACH_VEC_ELT (m_nodes, i, enode)
3769 : {
3770 112 : const supernode *iter_snode = enode->get_supernode ();
3771 112 : if (!iter_snode)
3772 5 : continue;
3773 107 : enodes_per_supernode[iter_snode->m_id]++;
3774 : }
3775 :
3776 : /* Accumulate excess enodes per supernode. */
3777 10 : auto_vec<unsigned> excess_enodes_per_supernode (m_sg.m_nodes.length ());
3778 90 : for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
3779 80 : excess_enodes_per_supernode.quick_push (0);
3780 83 : for (point_map_t::iterator iter = m_per_point_data.begin ();
3781 83 : iter != m_per_point_data.end (); ++iter)
3782 : {
3783 78 : const program_point *point = (*iter).first;
3784 78 : const supernode *iter_snode = point->get_supernode ();
3785 78 : if (!iter_snode)
3786 5 : continue;
3787 73 : const per_program_point_data *point_data = (*iter).second;
3788 73 : excess_enodes_per_supernode[iter_snode->m_id]
3789 73 : += point_data->m_excess_enodes;
3790 : }
3791 :
3792 : /* Show per-function bar_charts of enodes per supernode/BB. */
3793 5 : pp_string (pp, "per-function enodes per supernode/BB:");
3794 5 : pp_newline (pp);
3795 11 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode)
3796 : {
3797 6 : function *fn = cgnode->get_fun ();
3798 6 : pp_printf (pp, "function: %qs", function_name (fn));
3799 6 : pp_newline (pp);
3800 :
3801 6 : bar_chart enodes_per_snode;
3802 6 : bar_chart excess_enodes_per_snode;
3803 6 : bool have_excess_enodes = false;
3804 112 : for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
3805 : {
3806 106 : const supernode *iter_snode = m_sg.m_nodes[i];
3807 106 : if (iter_snode->get_function () != fn)
3808 26 : continue;
3809 80 : pretty_printer tmp_pp;
3810 80 : pp_printf (&tmp_pp, "sn %i (bb %i)",
3811 80 : iter_snode->m_id, iter_snode->m_bb->index);
3812 80 : enodes_per_snode.add_item (pp_formatted_text (&tmp_pp),
3813 80 : enodes_per_supernode[iter_snode->m_id]);
3814 80 : const int num_excess
3815 80 : = excess_enodes_per_supernode[iter_snode->m_id];
3816 80 : excess_enodes_per_snode.add_item (pp_formatted_text (&tmp_pp),
3817 : num_excess);
3818 80 : if (num_excess)
3819 0 : have_excess_enodes = true;
3820 80 : }
3821 6 : enodes_per_snode.print (pp);
3822 6 : if (have_excess_enodes)
3823 : {
3824 0 : pp_printf (pp, "EXCESS ENODES:");
3825 0 : pp_newline (pp);
3826 0 : excess_enodes_per_snode.print (pp);
3827 : }
3828 6 : }
3829 5 : }
3830 :
3831 : /* Write all stats information to this graph's logger, if any. */
3832 :
3833 : void
3834 3573 : exploded_graph::log_stats () const
3835 : {
3836 3573 : logger * const logger = get_logger ();
3837 3573 : if (!logger)
3838 3568 : return;
3839 :
3840 5 : LOG_SCOPE (logger);
3841 :
3842 5 : m_ext_state.get_engine ()->log_stats (logger);
3843 :
3844 10 : logger->log ("m_sg.num_nodes (): %i", m_sg.num_nodes ());
3845 10 : logger->log ("m_nodes.length (): %i", m_nodes.length ());
3846 10 : logger->log ("m_edges.length (): %i", m_edges.length ());
3847 5 : logger->log ("remaining enodes in worklist: %i", m_worklist.length ());
3848 :
3849 5 : logger->log ("global stats:");
3850 5 : m_global_stats.log (logger);
3851 :
3852 5 : for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
3853 22 : iter != m_per_function_stats.end ();
3854 6 : ++iter)
3855 : {
3856 6 : function *fn = (*iter).first;
3857 6 : log_scope s (logger, function_name (fn));
3858 6 : (*iter).second->log (logger);
3859 6 : }
3860 :
3861 5 : print_bar_charts (logger->get_printer ());
3862 5 : }
3863 :
3864 : /* Dump all stats information to OUT. */
3865 :
3866 : void
3867 0 : exploded_graph::dump_stats (FILE *out) const
3868 : {
3869 0 : fprintf (out, "m_sg.num_nodes (): %i\n", m_sg.num_nodes ());
3870 0 : fprintf (out, "m_nodes.length (): %i\n", m_nodes.length ());
3871 0 : fprintf (out, "m_edges.length (): %i\n", m_edges.length ());
3872 0 : fprintf (out, "remaining enodes in worklist: %i", m_worklist.length ());
3873 :
3874 0 : fprintf (out, "global stats:\n");
3875 0 : m_global_stats.dump (out);
3876 :
3877 0 : for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
3878 0 : iter != m_per_function_stats.end ();
3879 0 : ++iter)
3880 : {
3881 0 : function *fn = (*iter).first;
3882 0 : fprintf (out, "function: %s\n", function_name (fn));
3883 0 : (*iter).second->dump (out);
3884 : }
3885 0 : }
3886 :
3887 : /* Return a new json::object of the form
3888 : {"nodes" : [objs for enodes],
3889 : "edges" : [objs for eedges],
3890 : "ext_state": object for extrinsic_state,
3891 : "diagnostic_manager": object for diagnostic_manager}. */
3892 :
3893 : std::unique_ptr<json::object>
3894 0 : exploded_graph::to_json () const
3895 : {
3896 0 : auto egraph_obj = std::make_unique<json::object> ();
3897 :
3898 : /* Nodes. */
3899 0 : {
3900 0 : auto nodes_arr = std::make_unique<json::array> ();
3901 0 : unsigned i;
3902 0 : exploded_node *n;
3903 0 : FOR_EACH_VEC_ELT (m_nodes, i, n)
3904 0 : nodes_arr->append (n->to_json (m_ext_state));
3905 0 : egraph_obj->set ("nodes", std::move (nodes_arr));
3906 0 : }
3907 :
3908 : /* Edges. */
3909 0 : {
3910 0 : auto edges_arr = std::make_unique<json::array> ();
3911 0 : unsigned i;
3912 0 : exploded_edge *n;
3913 0 : FOR_EACH_VEC_ELT (m_edges, i, n)
3914 0 : edges_arr->append (n->to_json ());
3915 0 : egraph_obj->set ("edges", std::move (edges_arr));
3916 0 : }
3917 :
3918 : /* m_sg is JSONified at the top-level. */
3919 :
3920 0 : egraph_obj->set ("ext_state", m_ext_state.to_json ());
3921 0 : egraph_obj->set ("worklist", m_worklist.to_json ());
3922 0 : egraph_obj->set ("diagnostic_manager", m_diagnostic_manager.to_json ());
3923 :
3924 : /* The following fields aren't yet being JSONified:
3925 : const state_purge_map *const m_purge_map;
3926 : const analysis_plan &m_plan;
3927 : stats m_global_stats;
3928 : function_stat_map_t m_per_function_stats;
3929 : stats m_functionless_stats;
3930 : call_string_data_map_t m_per_call_string_data; */
3931 :
3932 0 : return egraph_obj;
3933 : }
3934 :
3935 : /* class feasibility_problem. */
3936 :
3937 : std::unique_ptr<text_art::tree_widget>
3938 0 : feasibility_problem::make_dump_widget (symbolic::node_dump_state &nds) const
3939 : {
3940 0 : std::unique_ptr<text_art::tree_widget> w
3941 0 : (text_art::tree_widget::make (nds, "feasibility_problem"));
3942 :
3943 0 : {
3944 0 : pretty_printer pp;
3945 0 : pp_printf (&pp, "edge from EN: %i to EN: %i",
3946 0 : m_eedge.m_src->m_index, m_eedge.m_dest->m_index);
3947 0 : w->add_child (text_art::tree_widget::make (nds, &pp));
3948 0 : }
3949 :
3950 0 : if (m_rc)
3951 : {
3952 0 : auto rc_w = (text_art::tree_widget::make (nds, "rejected_constraint"));
3953 0 : pretty_printer pp;
3954 0 : pp_format_decoder (&pp) = default_tree_printer;
3955 0 : m_rc->dump_to_pp (&pp);
3956 0 : rc_w->add_child (text_art::tree_widget::make (nds, &pp));
3957 0 : rc_w->add_child (m_rc->get_model ().make_dump_widget (nds));
3958 0 : w->add_child (std::move (rc_w));
3959 0 : }
3960 :
3961 0 : return w;
3962 : }
3963 :
3964 : DEBUG_FUNCTION void
3965 0 : feasibility_problem::dump () const
3966 : {
3967 0 : symbolic::dump_node_tree_to_stderr<feasibility_problem> (*this);
3968 0 : }
3969 :
3970 : void
3971 4 : feasibility_problem::dump_to_pp (pretty_printer *pp) const
3972 : {
3973 4 : text_art::theme *theme = global_dc->get_diagram_theme ();
3974 4 : symbolic::dump_node_tree_to_pp<feasibility_problem> (*this, theme, pp,
3975 : true, true);
3976 4 : }
3977 :
3978 : void
3979 0 : feasibility_problem::dump_to_logger (logger &log) const
3980 : {
3981 0 : symbolic::dump_node_tree_to_logger<feasibility_problem> (*this, log);
3982 0 : }
3983 :
3984 : std::unique_ptr<json::object>
3985 0 : feasibility_problem::to_json () const
3986 : {
3987 0 : auto obj = std::make_unique<json::object> ();
3988 :
3989 0 : obj->set_integer ("eedge_idx", m_eedge_idx);
3990 0 : obj->set_integer ("eedge src enode", m_eedge.m_src->m_index);
3991 0 : obj->set_integer ("eedge dst enode", m_eedge.m_dest->m_index);
3992 0 : if (m_rc)
3993 0 : obj->set <json::object> ("rejected_constraint", m_rc->to_json ());
3994 :
3995 0 : return obj;
3996 : }
3997 :
3998 : /* class feasibility_state. */
3999 :
4000 : /* Ctor for feasibility_state, at the beginning of a path. */
4001 :
4002 6671 : feasibility_state::feasibility_state (region_model_manager *manager,
4003 : const supergraph &sg)
4004 6671 : : m_model (manager->get_node_manager ()),
4005 13342 : m_snodes_visited (sg.m_nodes.length ())
4006 : {
4007 6671 : bitmap_clear (m_snodes_visited);
4008 6671 : }
4009 :
4010 : /* Copy ctor for feasibility_state, for extending a path. */
4011 :
4012 296501 : feasibility_state::feasibility_state (const feasibility_state &other)
4013 296501 : : m_model (other.m_model),
4014 296501 : m_snodes_visited (const_sbitmap (other.m_snodes_visited)->n_bits)
4015 : {
4016 296501 : bitmap_copy (m_snodes_visited, other.m_snodes_visited);
4017 296501 : }
4018 :
4019 31207 : feasibility_state::feasibility_state (const region_model &model,
4020 : const supergraph &sg)
4021 31207 : : m_model (model),
4022 62414 : m_snodes_visited (sg.m_nodes.length ())
4023 : {
4024 31207 : bitmap_clear (m_snodes_visited);
4025 31207 : }
4026 :
4027 : feasibility_state &
4028 19297 : feasibility_state::operator= (const feasibility_state &other)
4029 : {
4030 19297 : m_model = other.m_model;
4031 19297 : bitmap_copy (m_snodes_visited, other.m_snodes_visited);
4032 19297 : return *this;
4033 : }
4034 :
4035 : /* The heart of feasibility-checking.
4036 :
4037 : Attempt to update this state in-place based on traversing EEDGE
4038 : in a path.
4039 : Update the model for the stmts in the src enode.
4040 : Attempt to add constraints for EEDGE.
4041 :
4042 : If feasible, return true.
4043 : Otherwise, return false and write to *OUT_RC. */
4044 :
4045 : bool
4046 137613 : feasibility_state::
4047 : maybe_update_for_edge (logger *logger,
4048 : const exploded_edge *eedge,
4049 : region_model_context *ctxt,
4050 : std::unique_ptr<rejected_constraint> *out_rc)
4051 : {
4052 137613 : const exploded_node &src_enode = *eedge->m_src;
4053 137613 : const program_point &src_point = src_enode.get_point ();
4054 137613 : if (logger)
4055 : {
4056 44 : logger->start_log_line ();
4057 44 : src_point.print (logger->get_printer (), format (false));
4058 44 : logger->end_log_line ();
4059 : }
4060 :
4061 137613 : if (eedge->m_custom_info)
4062 7770 : eedge->m_custom_info->update_model (&m_model, eedge, ctxt);
4063 : else
4064 : {
4065 129843 : const superedge *sedge = eedge->m_sedge;
4066 129843 : if (sedge)
4067 : {
4068 122255 : if (logger)
4069 : {
4070 42 : label_text desc (sedge->get_description (false));
4071 42 : logger->log (" sedge: SN:%i -> SN:%i %s",
4072 42 : sedge->m_src->m_id,
4073 42 : sedge->m_dest->m_id,
4074 : desc.get ());
4075 42 : }
4076 :
4077 122255 : if (sedge->get_op ())
4078 91378 : if (!sedge->get_op ()->execute_for_feasibility (*eedge,
4079 : *this,
4080 : ctxt,
4081 : out_rc))
4082 : {
4083 5795 : if (logger)
4084 : {
4085 3 : logger->log ("rejecting due to region model: ");
4086 3 : m_model.dump_to_logger (*logger);
4087 : }
4088 : return false;
4089 : }
4090 : }
4091 : else
4092 : {
4093 : /* Special-case the initial eedge from the origin node to the
4094 : initial function by pushing a frame for it. */
4095 7588 : if (eedge->m_src->m_index == 0)
4096 : {
4097 6497 : function *fun = eedge->m_dest->get_function ();
4098 6497 : gcc_assert (fun);
4099 6497 : m_model.push_frame (*fun, nullptr, nullptr, ctxt);
4100 6497 : if (logger)
4101 2 : logger->log (" pushing frame for %qD", fun->decl);
4102 : }
4103 : }
4104 : }
4105 :
4106 :
4107 131818 : {
4108 131818 : const exploded_node &dst_enode = *eedge->m_dest;
4109 131818 : const unsigned dst_snode_idx = dst_enode.get_supernode ()->m_id;
4110 131818 : bitmap_set_bit (m_snodes_visited, dst_snode_idx);
4111 : }
4112 :
4113 131818 : return true;
4114 : }
4115 :
4116 : std::unique_ptr<text_art::tree_widget>
4117 0 : feasibility_state::make_dump_widget (symbolic::node_dump_state &nds) const
4118 : {
4119 0 : using text_art::tree_widget;
4120 0 : std::unique_ptr<tree_widget> fs_widget
4121 0 : (tree_widget::from_fmt (nds, nullptr, "feasibility_state"));
4122 :
4123 0 : fs_widget->add_child (m_model.make_dump_widget (nds));
4124 : // TODO: m_snodes_visited;
4125 0 : return fs_widget;
4126 : }
4127 :
4128 : /* Dump a tree-like representation of this feasibility_state to PP. */
4129 :
4130 : void
4131 70 : feasibility_state::dump_to_pp (pretty_printer *pp) const
4132 : {
4133 70 : text_art::theme *theme = global_dc->get_diagram_theme ();
4134 70 : symbolic::dump_node_tree_to_pp<feasibility_state> (*this, theme, pp, true, true);
4135 70 : }
4136 :
4137 : /* A family of cluster subclasses for use when generating .dot output for
4138 : exploded graphs (-fdump-analyzer-exploded-graph), for grouping the
4139 : enodes into hierarchical boxes.
4140 :
4141 : All functionless enodes appear in the top-level graph.
4142 : Every (function, call_string) pair gets its own cluster. Within that
4143 : cluster, each supernode gets its own cluster.
4144 :
4145 : Hence all enodes relating to a particular function with a particular
4146 : callstring will be in a cluster together; all enodes for the same
4147 : function but with a different callstring will be in a different
4148 : cluster. */
4149 :
4150 : /* Base class of cluster for clustering exploded_node instances in .dot
4151 : output, based on various subclass-specific criteria. */
4152 :
4153 1315 : class exploded_cluster : public cluster<eg_traits>
4154 : {
4155 : };
4156 :
4157 : /* Cluster containing all exploded_node instances for one supernode. */
4158 :
4159 : class supernode_cluster : public exploded_cluster
4160 : {
4161 : public:
4162 437 : supernode_cluster (const supernode *supernode) : m_supernode (supernode) {}
4163 :
4164 : // TODO: dtor?
4165 :
4166 437 : void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
4167 : {
4168 437 : gv->println ("subgraph \"cluster_supernode_%i\" {", m_supernode->m_id);
4169 437 : gv->indent ();
4170 437 : gv->println ("style=\"dashed\";");
4171 874 : gv->println ("label=\"SN: %i (bb: %i; scc: %i)\";",
4172 437 : m_supernode->m_id, m_supernode->m_bb->index,
4173 437 : args.m_eg.get_scc_id (*m_supernode));
4174 :
4175 437 : int i;
4176 437 : exploded_node *enode;
4177 1311 : FOR_EACH_VEC_ELT (m_enodes, i, enode)
4178 437 : enode->dump_dot (gv, args);
4179 :
4180 : /* Terminate subgraph. */
4181 437 : gv->outdent ();
4182 437 : gv->println ("}");
4183 437 : }
4184 :
4185 437 : void add_node (exploded_node *en) final override
4186 : {
4187 0 : m_enodes.safe_push (en);
4188 0 : }
4189 :
4190 : /* Comparator for use by auto_vec<supernode_cluster *>::qsort. */
4191 :
4192 0 : static int cmp_ptr_ptr (const void *p1, const void *p2)
4193 : {
4194 0 : const supernode_cluster *c1
4195 : = *(const supernode_cluster * const *)p1;
4196 0 : const supernode_cluster *c2
4197 : = *(const supernode_cluster * const *)p2;
4198 0 : return c1->m_supernode->m_id - c2->m_supernode->m_id;
4199 : }
4200 :
4201 : private:
4202 : const supernode *m_supernode;
4203 : auto_vec <exploded_node *> m_enodes;
4204 : };
4205 :
4206 : /* Cluster containing all supernode_cluster instances for one
4207 : (function, call_string) pair. */
4208 :
4209 : class function_call_string_cluster : public exploded_cluster
4210 : {
4211 : public:
4212 437 : function_call_string_cluster (function *fun, const call_string &cs)
4213 437 : : m_fun (fun), m_cs (cs) {}
4214 :
4215 874 : ~function_call_string_cluster ()
4216 437 : {
4217 437 : for (map_t::iterator iter = m_map.begin ();
4218 1748 : iter != m_map.end ();
4219 437 : ++iter)
4220 437 : delete (*iter).second;
4221 874 : }
4222 :
4223 437 : void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
4224 : {
4225 437 : const char *funcname = function_name (m_fun);
4226 :
4227 874 : gv->println ("subgraph \"cluster_function_%s\" {",
4228 437 : IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (m_fun->decl)));
4229 437 : gv->indent ();
4230 437 : gv->write_indent ();
4231 437 : gv->print ("label=\"call string: ");
4232 437 : m_cs.print (gv->get_pp ());
4233 437 : gv->print (" function: %s \";", funcname);
4234 437 : gv->print ("\n");
4235 :
4236 : /* Dump m_map, sorting it to avoid churn when comparing dumps. */
4237 437 : auto_vec<supernode_cluster *> child_clusters (m_map.elements ());
4238 437 : for (map_t::iterator iter = m_map.begin ();
4239 1748 : iter != m_map.end ();
4240 437 : ++iter)
4241 437 : child_clusters.quick_push ((*iter).second);
4242 :
4243 437 : child_clusters.qsort (supernode_cluster::cmp_ptr_ptr);
4244 :
4245 437 : unsigned i;
4246 437 : supernode_cluster *child_cluster;
4247 874 : FOR_EACH_VEC_ELT (child_clusters, i, child_cluster)
4248 437 : child_cluster->dump_dot (gv, args);
4249 :
4250 : /* Terminate subgraph. */
4251 437 : gv->outdent ();
4252 437 : gv->println ("}");
4253 437 : }
4254 :
4255 437 : void add_node (exploded_node *en) final override
4256 : {
4257 437 : const supernode *supernode = en->get_supernode ();
4258 437 : gcc_assert (supernode);
4259 437 : supernode_cluster **slot = m_map.get (supernode);
4260 437 : if (slot)
4261 0 : (*slot)->add_node (en);
4262 : else
4263 : {
4264 437 : supernode_cluster *child = new supernode_cluster (supernode);
4265 437 : m_map.put (supernode, child);
4266 437 : child->add_node (en);
4267 : }
4268 437 : }
4269 :
4270 : /* Comparator for use by auto_vec<function_call_string_cluster *>. */
4271 :
4272 18054 : static int cmp_ptr_ptr (const void *p1, const void *p2)
4273 : {
4274 18054 : const function_call_string_cluster *c1
4275 : = *(const function_call_string_cluster * const *)p1;
4276 18054 : const function_call_string_cluster *c2
4277 : = *(const function_call_string_cluster * const *)p2;
4278 36108 : if (int cmp_names
4279 18054 : = strcmp (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c1->m_fun->decl)),
4280 18054 : IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c2->m_fun->decl))))
4281 : return cmp_names;
4282 5071 : return call_string::cmp (c1->m_cs, c2->m_cs);
4283 : }
4284 :
4285 : private:
4286 : function *m_fun;
4287 : const call_string &m_cs;
4288 : typedef ordered_hash_map<const supernode *, supernode_cluster *> map_t;
4289 : map_t m_map;
4290 : };
4291 :
4292 : /* Keys for root_cluster. */
4293 :
4294 : struct function_call_string
4295 : {
4296 437 : function_call_string (function *fun, const call_string *cs)
4297 437 : : m_fun (fun), m_cs (cs)
4298 : {
4299 437 : gcc_assert (fun);
4300 437 : gcc_assert (cs);
4301 437 : }
4302 :
4303 : function *m_fun;
4304 : const call_string *m_cs;
4305 : };
4306 :
4307 : } // namespace ana
4308 :
4309 : template <> struct default_hash_traits<function_call_string>
4310 : : public pod_hash_traits<function_call_string>
4311 : {
4312 : static const bool empty_zero_p = false;
4313 : };
4314 :
4315 : template <>
4316 : inline hashval_t
4317 6421 : pod_hash_traits<function_call_string>::hash (value_type v)
4318 : {
4319 6421 : return (pointer_hash <function>::hash (v.m_fun)
4320 6421 : ^ pointer_hash <const call_string>::hash (v.m_cs));
4321 : }
4322 :
4323 : template <>
4324 : inline bool
4325 31400 : pod_hash_traits<function_call_string>::equal (const value_type &existing,
4326 : const value_type &candidate)
4327 : {
4328 31400 : return existing.m_fun == candidate.m_fun && &existing.m_cs == &candidate.m_cs;
4329 : }
4330 : template <>
4331 : inline void
4332 : pod_hash_traits<function_call_string>::mark_deleted (value_type &v)
4333 : {
4334 : v.m_fun = reinterpret_cast<function *> (1);
4335 : }
4336 : template <>
4337 : inline void
4338 1932 : pod_hash_traits<function_call_string>::mark_empty (value_type &v)
4339 : {
4340 1932 : v.m_fun = nullptr;
4341 : }
4342 : template <>
4343 : inline bool
4344 49193 : pod_hash_traits<function_call_string>::is_deleted (value_type v)
4345 : {
4346 49193 : return v.m_fun == reinterpret_cast<function *> (1);
4347 : }
4348 : template <>
4349 : inline bool
4350 107971 : pod_hash_traits<function_call_string>::is_empty (value_type v)
4351 : {
4352 107534 : return v.m_fun == nullptr;
4353 : }
4354 :
4355 : namespace ana {
4356 :
4357 : /* Top-level cluster for generating .dot output for exploded graphs,
4358 : handling the functionless nodes, and grouping the remaining nodes by
4359 : callstring. */
4360 :
4361 : class root_cluster : public exploded_cluster
4362 : {
4363 : public:
4364 4 : ~root_cluster ()
4365 4 : {
4366 441 : for (map_t::iterator iter = m_map.begin ();
4367 441 : iter != m_map.end ();
4368 437 : ++iter)
4369 437 : delete (*iter).second;
4370 4 : }
4371 :
4372 4 : void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
4373 : {
4374 4 : int i;
4375 4 : exploded_node *enode;
4376 8 : FOR_EACH_VEC_ELT (m_functionless_enodes, i, enode)
4377 4 : enode->dump_dot (gv, args);
4378 :
4379 : /* Dump m_map, sorting it to avoid churn when comparing dumps. */
4380 4 : auto_vec<function_call_string_cluster *> child_clusters (m_map.elements ());
4381 4 : for (map_t::iterator iter = m_map.begin ();
4382 441 : iter != m_map.end ();
4383 437 : ++iter)
4384 437 : child_clusters.quick_push ((*iter).second);
4385 :
4386 4 : child_clusters.qsort (function_call_string_cluster::cmp_ptr_ptr);
4387 :
4388 4 : function_call_string_cluster *child_cluster;
4389 445 : FOR_EACH_VEC_ELT (child_clusters, i, child_cluster)
4390 437 : child_cluster->dump_dot (gv, args);
4391 4 : }
4392 :
4393 441 : void add_node (exploded_node *en) final override
4394 : {
4395 441 : function *fun = en->get_function ();
4396 437 : if (!fun)
4397 : {
4398 4 : m_functionless_enodes.safe_push (en);
4399 4 : return;
4400 : }
4401 :
4402 437 : const call_string &cs = en->get_point ().get_call_string ();
4403 437 : function_call_string key (fun, &cs);
4404 437 : function_call_string_cluster **slot = m_map.get (key);
4405 437 : if (slot)
4406 0 : (*slot)->add_node (en);
4407 : else
4408 : {
4409 437 : function_call_string_cluster *child
4410 437 : = new function_call_string_cluster (fun, cs);
4411 437 : m_map.put (key, child);
4412 437 : child->add_node (en);
4413 : }
4414 : }
4415 :
4416 : private:
4417 : typedef hash_map<function_call_string, function_call_string_cluster *> map_t;
4418 : map_t m_map;
4419 :
4420 : /* This should just be the origin exploded_node. */
4421 : auto_vec <exploded_node *> m_functionless_enodes;
4422 : };
4423 :
4424 : /* Subclass of range_label for use within
4425 : exploded_graph::dump_exploded_nodes for implementing
4426 : -fdump-analyzer-exploded-nodes: a label for a specific
4427 : exploded_node. */
4428 :
4429 : class enode_label : public range_label
4430 : {
4431 : public:
4432 0 : enode_label (const extrinsic_state &ext_state,
4433 : exploded_node *enode)
4434 0 : : m_ext_state (ext_state), m_enode (enode) {}
4435 :
4436 0 : label_text get_text (unsigned) const final override
4437 : {
4438 0 : return make_label_text (false, "EN: %i", m_enode->m_index);
4439 : }
4440 :
4441 : private:
4442 : const extrinsic_state &m_ext_state;
4443 : exploded_node *m_enode;
4444 : };
4445 :
4446 : /* Postprocessing support for dumping the exploded nodes.
4447 : Handle -fdump-analyzer-exploded-nodes,
4448 : -fdump-analyzer-exploded-nodes-2, and the
4449 : "__analyzer_dump_exploded_nodes" builtin. */
4450 :
4451 : void
4452 3573 : exploded_graph::dump_exploded_nodes () const
4453 : {
4454 : // TODO
4455 : /* Locate calls to __analyzer_dump_exploded_nodes. */
4456 : // Print how many egs there are for them?
4457 : /* Better: log them as we go, and record the exploded nodes
4458 : in question. */
4459 :
4460 : /* Show every enode. */
4461 :
4462 : /* Gather them by stmt, so that we can more clearly see the
4463 : "hotspots" requiring numerous exploded nodes. */
4464 :
4465 : /* Alternatively, simply throw them all into one big rich_location
4466 : and see if the label-printing will sort it out...
4467 : This requires them all to be in the same source file. */
4468 :
4469 3573 : if (flag_dump_analyzer_exploded_nodes)
4470 : {
4471 0 : auto_timevar tv (TV_ANALYZER_DUMP);
4472 0 : gcc_rich_location richloc (UNKNOWN_LOCATION);
4473 0 : unsigned i;
4474 0 : exploded_node *enode;
4475 0 : FOR_EACH_VEC_ELT (m_nodes, i, enode)
4476 : {
4477 0 : location_t loc = enode->get_location ();
4478 0 : if (get_pure_location (richloc.get_loc ()) == UNKNOWN_LOCATION)
4479 0 : richloc.set_range (0, loc, SHOW_RANGE_WITH_CARET);
4480 : else
4481 0 : richloc.add_range (loc,
4482 : SHOW_RANGE_WITHOUT_CARET,
4483 0 : new enode_label (m_ext_state, enode));
4484 : }
4485 0 : warning_at (&richloc, 0, "%i exploded nodes", m_nodes.length ());
4486 :
4487 : /* Repeat the warning without all the labels, so that message is visible
4488 : (the other one may well have scrolled past the terminal limit). */
4489 0 : warning_at (richloc.get_loc (), 0,
4490 : "%i exploded nodes", m_nodes.length ());
4491 :
4492 0 : if (m_worklist.length () > 0)
4493 0 : warning_at (richloc.get_loc (), 0,
4494 : "worklist still contains %i nodes", m_worklist.length ());
4495 0 : }
4496 :
4497 : /* Dump the egraph in textual form to a dump file. */
4498 3573 : if (flag_dump_analyzer_exploded_nodes_2)
4499 : {
4500 0 : auto_timevar tv (TV_ANALYZER_DUMP);
4501 0 : char *filename
4502 0 : = concat (dump_base_name, ".eg.txt", nullptr);
4503 0 : FILE *outf = fopen (filename, "w");
4504 0 : if (!outf)
4505 0 : error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
4506 0 : free (filename);
4507 :
4508 0 : fprintf (outf, "exploded graph for %s\n", dump_base_name);
4509 0 : fprintf (outf, " nodes: %i\n", m_nodes.length ());
4510 0 : fprintf (outf, " edges: %i\n", m_edges.length ());
4511 :
4512 0 : unsigned i;
4513 0 : exploded_node *enode;
4514 0 : FOR_EACH_VEC_ELT (m_nodes, i, enode)
4515 : {
4516 0 : fprintf (outf, "\nEN %i:\n", enode->m_index);
4517 0 : enode->dump_succs_and_preds (outf);
4518 0 : pretty_printer pp;
4519 0 : enode->get_point ().print (&pp, format (true));
4520 0 : fprintf (outf, "%s\n", pp_formatted_text (&pp));
4521 0 : symbolic::dump_node_tree_to_file<program_state> (enode->get_state (), outf);
4522 0 : }
4523 :
4524 0 : fclose (outf);
4525 0 : }
4526 :
4527 : /* Dump the egraph in textual form to multiple dump files, one per enode. */
4528 3573 : if (flag_dump_analyzer_exploded_nodes_3)
4529 : {
4530 0 : auto_timevar tv (TV_ANALYZER_DUMP);
4531 :
4532 0 : unsigned i;
4533 0 : exploded_node *enode;
4534 0 : FOR_EACH_VEC_ELT (m_nodes, i, enode)
4535 : {
4536 0 : char *filename
4537 0 : = xasprintf ("%s.en-%i.txt", dump_base_name, i);
4538 0 : FILE *outf = fopen (filename, "w");
4539 0 : if (!outf)
4540 0 : error_at (UNKNOWN_LOCATION, "unable to open %qs for writing",
4541 : filename);
4542 0 : free (filename);
4543 :
4544 0 : fprintf (outf, "EN %i:\n", enode->m_index);
4545 0 : enode->dump_succs_and_preds (outf);
4546 0 : pretty_printer pp;
4547 0 : enode->get_point ().print (&pp, format (true));
4548 0 : fprintf (outf, "%s\n", pp_formatted_text (&pp));
4549 0 : symbolic::dump_node_tree_to_file<program_state> (enode->get_state (), outf);
4550 :
4551 0 : fclose (outf);
4552 0 : }
4553 0 : }
4554 :
4555 : /* Emit a warning at any call to "__analyzer_dump_exploded_nodes",
4556 : giving the number of processed exploded nodes at the snode before
4557 : the call, and the IDs of processed, merger, and worklist enodes.
4558 :
4559 : We highlight the count of *processed* enodes since this is of most
4560 : interest in DejaGnu tests for ensuring that state merger has
4561 : happened.
4562 :
4563 : We don't show the count of merger and worklist enodes, as this is
4564 : more of an implementation detail of the merging/worklist that we
4565 : don't want to bake into our expected DejaGnu messages. */
4566 :
4567 3573 : unsigned i;
4568 3573 : exploded_node *enode;
4569 3573 : hash_set<const gimple *> seen;
4570 381904 : FOR_EACH_VEC_ELT (m_nodes, i, enode)
4571 : {
4572 371189 : const supernode *snode = enode->get_supernode ();
4573 371189 : if (!snode)
4574 3569 : continue;
4575 367620 : if (snode->m_succs.length () != 1)
4576 44724 : continue;
4577 322896 : const superedge *sedge = snode->m_succs[0];
4578 322896 : if (!sedge->get_op ())
4579 87307 : continue;
4580 235589 : const call_and_return_op *op
4581 235589 : = sedge->get_op ()->dyn_cast_call_and_return_op ();
4582 235589 : if (!op)
4583 171457 : continue;
4584 64132 : const gcall &call = op->get_gcall ();
4585 64132 : if (is_special_named_call_p (call, "__analyzer_dump_exploded_nodes", 1))
4586 : {
4587 1185 : if (seen.contains (&call))
4588 484 : continue;
4589 :
4590 701 : auto_vec<exploded_node *> processed_enodes;
4591 701 : auto_vec<exploded_node *> merger_enodes;
4592 701 : auto_vec<exploded_node *> worklist_enodes;
4593 : /* This is O(N^2). */
4594 701 : unsigned j;
4595 701 : exploded_node *other_enode;
4596 126449 : FOR_EACH_VEC_ELT (m_nodes, j, other_enode)
4597 : {
4598 125047 : if (other_enode->get_supernode () == snode)
4599 1185 : switch (other_enode->get_status ())
4600 : {
4601 0 : default:
4602 0 : gcc_unreachable ();
4603 0 : case exploded_node::status::worklist:
4604 0 : worklist_enodes.safe_push (other_enode);
4605 0 : break;
4606 1116 : case exploded_node::status::processed:
4607 1116 : processed_enodes.safe_push (other_enode);
4608 1116 : break;
4609 69 : case exploded_node::status::merger:
4610 69 : merger_enodes.safe_push (other_enode);
4611 69 : break;
4612 : }
4613 : }
4614 :
4615 1402 : pretty_printer pp;
4616 701 : pp_character (&pp, '[');
4617 701 : print_enode_indices (&pp, processed_enodes);
4618 701 : if (merger_enodes.length () > 0)
4619 : {
4620 44 : pp_string (&pp, "] merger(s): [");
4621 44 : print_enode_indices (&pp, merger_enodes);
4622 : }
4623 701 : if (worklist_enodes.length () > 0)
4624 : {
4625 0 : pp_string (&pp, "] worklist: [");
4626 0 : print_enode_indices (&pp, worklist_enodes);
4627 : }
4628 701 : pp_character (&pp, ']');
4629 :
4630 1402 : warning_n (call.location, 0, processed_enodes.length (),
4631 : "%i processed enode: %s",
4632 : "%i processed enodes: %s",
4633 : processed_enodes.length (), pp_formatted_text (&pp));
4634 701 : seen.add (&call);
4635 :
4636 : /* If the argument is non-zero, then print all of the states
4637 : of the various enodes. */
4638 701 : tree t_arg = fold (gimple_call_arg (&call, 0));
4639 701 : if (TREE_CODE (t_arg) != INTEGER_CST)
4640 : {
4641 0 : error_at (snode->m_loc,
4642 : "integer constant required for arg 1");
4643 0 : return;
4644 : }
4645 701 : int i_arg = TREE_INT_CST_LOW (t_arg);
4646 701 : if (i_arg)
4647 : {
4648 : exploded_node *other_enode;
4649 701 : FOR_EACH_VEC_ELT (processed_enodes, j, other_enode)
4650 : {
4651 0 : fprintf (stderr, "%i of %i: EN %i:\n",
4652 : j + 1, processed_enodes.length (),
4653 0 : other_enode->m_index);
4654 0 : other_enode->dump_succs_and_preds (stderr);
4655 : /* Dump state. */
4656 0 : other_enode->get_state ().dump ();
4657 : }
4658 : }
4659 701 : }
4660 : }
4661 3573 : }
4662 :
4663 : DEBUG_FUNCTION exploded_node *
4664 0 : exploded_graph::get_node_by_index (int idx) const
4665 : {
4666 0 : exploded_node *enode = m_nodes[idx];
4667 0 : gcc_assert (enode->m_index == idx);
4668 0 : return enode;
4669 : }
4670 :
4671 : /* Ensure that there is an exploded_node for a top-level call to FNDECL. */
4672 :
4673 : void
4674 309 : exploded_graph::on_escaped_function (tree fndecl)
4675 : {
4676 309 : logger * const logger = get_logger ();
4677 309 : LOG_FUNC_1 (logger, "%qE", fndecl);
4678 :
4679 309 : cgraph_node *cgnode = cgraph_node::get (fndecl);
4680 309 : if (!cgnode)
4681 : return;
4682 :
4683 309 : function *fun = cgnode->get_fun ();
4684 309 : if (!fun)
4685 : return;
4686 :
4687 305 : if (!gimple_has_body_p (fndecl))
4688 : return;
4689 :
4690 305 : exploded_node *enode = add_function_entry (*fun);
4691 305 : if (logger)
4692 : {
4693 0 : if (enode)
4694 0 : logger->log ("created EN %i for %qE entrypoint",
4695 0 : enode->m_index, fun->decl);
4696 : else
4697 0 : logger->log ("did not create enode for %qE entrypoint", fun->decl);
4698 : }
4699 309 : }
4700 :
4701 : /* Subclass of dot_annotator for implementing
4702 : DUMP_BASE_NAME.supergraph.N.eg.dot, a post-analysis dump of the supergraph.
4703 :
4704 : Annotate the supergraph nodes by printing the exploded nodes in concise
4705 : form within them, colorizing the exploded nodes based on sm-state.
4706 : Also show saved diagnostics within the exploded nodes, giving information
4707 : on whether they were feasible, and, if infeasible, where the problem
4708 : was. */
4709 :
4710 4 : class exploded_graph_annotator : public dot_annotator
4711 : {
4712 : public:
4713 4 : exploded_graph_annotator (const exploded_graph &eg)
4714 4 : : m_eg (eg)
4715 : {
4716 : /* Avoid O(N^2) by prepopulating m_enodes_per_snode_id. */
4717 390 : for (size_t i = 0; i < eg.get_supergraph ().m_nodes.length (); ++i)
4718 191 : m_enodes_per_snode_id.push_back (std::vector<exploded_node *> ());
4719 : exploded_node *enode;
4720 : unsigned i;
4721 445 : FOR_EACH_VEC_ELT (m_eg.m_nodes, i, enode)
4722 441 : if (enode->get_supernode ())
4723 437 : m_enodes_per_snode_id[enode->get_supernode ()->m_id].push_back (enode);
4724 4 : }
4725 :
4726 : /* Show exploded nodes for N. */
4727 191 : void add_node_annotations (graphviz_out *gv, const supernode &n)
4728 : const final override
4729 : {
4730 191 : gv->begin_tr ();
4731 191 : pretty_printer *pp = gv->get_pp ();
4732 :
4733 191 : if (m_enodes_per_snode_id[n.m_id].empty ())
4734 4 : pp_string (pp, "<TD BGCOLOR=\"red\">UNREACHED</TD>");
4735 : else
4736 : {
4737 : /* Adding an empty TD here makes the actual enodes
4738 : be right-aligned and tightly packed, greatly
4739 : improving the readability of the graph. */
4740 187 : pp_string (pp, "<TD></TD>");
4741 624 : for (auto enode : m_enodes_per_snode_id[n.m_id])
4742 : {
4743 437 : gcc_assert (enode->get_supernode () == &n);
4744 437 : print_enode (gv, enode);
4745 : }
4746 : }
4747 :
4748 191 : pp_flush (pp);
4749 191 : gv->end_tr ();
4750 191 : }
4751 :
4752 : void
4753 4 : add_extra_objects (graphviz_out *gv) const final override
4754 : {
4755 4 : pretty_printer *pp = gv->get_pp ();
4756 :
4757 4 : pp_string (pp, "en_0 [shape=none,margin=0,style=filled,label=<<TABLE><TR>");
4758 4 : print_enode (gv, m_eg.m_nodes[0]);
4759 4 : pp_string (pp, "</TR></TABLE>>];\n\n");
4760 4 : pp_flush (pp);
4761 :
4762 4 : unsigned i;
4763 4 : exploded_edge *eedge;
4764 461 : FOR_EACH_VEC_ELT (m_eg.m_edges, i, eedge)
4765 : {
4766 453 : print_enode_port (pp, *eedge->m_src, "s");
4767 453 : pp_string (pp, " -> ");
4768 453 : print_enode_port (pp, *eedge->m_dest, "n");
4769 453 : dot::attr_list attrs;
4770 453 : attrs.add (dot::id ("style"), dot::id ("dotted"));
4771 453 : if (eedge->m_custom_info)
4772 : {
4773 22 : pretty_printer info_pp;
4774 22 : pp_format_decoder (&info_pp) = default_tree_printer;
4775 22 : eedge->m_custom_info->print (&info_pp);
4776 22 : attrs.add (dot::id ("label"),
4777 44 : dot::id (pp_formatted_text (&info_pp)));
4778 22 : }
4779 453 : dot::writer w (*pp);
4780 453 : attrs.print (w);
4781 453 : pp_newline (pp);
4782 453 : }
4783 4 : }
4784 :
4785 : private:
4786 : void
4787 906 : print_enode_port (pretty_printer *pp,
4788 : const exploded_node &enode,
4789 : const char *compass_pt) const
4790 : {
4791 906 : if (const supernode *snode = enode.get_supernode ())
4792 : {
4793 894 : snode->dump_dot_id (pp);
4794 894 : pp_printf (pp, ":en_%i:%s",
4795 894 : enode.m_index, compass_pt);
4796 : }
4797 : else
4798 12 : pp_printf (pp, "en_%i:%s",
4799 12 : enode.m_index, compass_pt);
4800 906 : }
4801 :
4802 : /* Concisely print a TD element for ENODE, showing the index, status,
4803 : and any saved_diagnostics at the enode. Colorize it to show sm-state.
4804 :
4805 : Ideally we'd dump ENODE's state here, hidden behind some kind of
4806 : interactive disclosure method like a tooltip, so that the states
4807 : can be explored without overwhelming the graph.
4808 : However, I wasn't able to get graphviz/xdot to show tooltips on
4809 : individual elements within a HTML-like label. */
4810 441 : void print_enode (graphviz_out *gv, const exploded_node *enode) const
4811 : {
4812 441 : pretty_printer *pp = gv->get_pp ();
4813 441 : pp_printf (pp, "<TD BGCOLOR=\"%s\">",
4814 : enode->get_dot_fillcolor ());
4815 441 : pp_printf (pp, "<TABLE BORDER=\"0\" PORT=\"en_%i\">", enode->m_index);
4816 441 : gv->begin_trtd ();
4817 441 : pp_printf (pp, "EN: %i", enode->m_index);
4818 441 : switch (enode->get_status ())
4819 : {
4820 0 : default:
4821 0 : gcc_unreachable ();
4822 0 : case exploded_node::status::worklist:
4823 0 : pp_string (pp, "(W)");
4824 0 : break;
4825 : case exploded_node::status::processed:
4826 : break;
4827 6 : case exploded_node::status::special:
4828 6 : pp_string (pp, "(S)");
4829 6 : break;
4830 12 : case exploded_node::status::merger:
4831 12 : pp_string (pp, "(M)");
4832 12 : break;
4833 0 : case exploded_node::status::bulk_merged:
4834 0 : pp_string (pp, "(BM)");
4835 0 : break;
4836 : }
4837 441 : gv->end_tdtr ();
4838 :
4839 : /* Dump any saved_diagnostics at this enode. */
4840 886 : for (unsigned i = 0; i < enode->get_num_diagnostics (); i++)
4841 : {
4842 4 : const saved_diagnostic *sd = enode->get_saved_diagnostic (i);
4843 4 : print_saved_diagnostic (gv, sd);
4844 : }
4845 441 : pp_printf (pp, "</TABLE>");
4846 441 : pp_printf (pp, "</TD>");
4847 441 : }
4848 :
4849 : /* Print a TABLE element for SD, showing the kind, the length of the
4850 : exploded_path, whether the path was feasible, and if infeasible,
4851 : what the problem was. */
4852 4 : void print_saved_diagnostic (graphviz_out *gv,
4853 : const saved_diagnostic *sd) const
4854 : {
4855 4 : pretty_printer *pp = gv->get_pp ();
4856 4 : gv->begin_trtd ();
4857 4 : pp_printf (pp, "<TABLE BORDER=\"0\">");
4858 4 : gv->begin_tr ();
4859 4 : pp_string (pp, "<TD BGCOLOR=\"green\">");
4860 4 : pp_printf (pp, "DIAGNOSTIC: %s", sd->m_d->get_kind ());
4861 4 : gv->end_tdtr ();
4862 4 : gv->begin_trtd ();
4863 4 : if (sd->get_best_epath ())
4864 4 : pp_printf (pp, "epath length: %i", sd->get_epath_length ());
4865 : else
4866 0 : pp_printf (pp, "no best epath");
4867 4 : gv->end_tdtr ();
4868 4 : if (const feasibility_problem *p = sd->get_feasibility_problem ())
4869 : {
4870 0 : gv->begin_trtd ();
4871 0 : pp_printf (pp, "INFEASIBLE at eedge %i: EN:%i -> EN:%i",
4872 0 : p->m_eedge_idx,
4873 0 : p->m_eedge.m_src->m_index,
4874 0 : p->m_eedge.m_dest->m_index);
4875 0 : pp_write_text_as_html_like_dot_to_stream (pp);
4876 0 : gv->end_tdtr ();
4877 0 : gv->begin_trtd ();
4878 0 : p->m_eedge.m_sedge->dump (pp);
4879 0 : pp_write_text_as_html_like_dot_to_stream (pp);
4880 0 : gv->end_tdtr ();
4881 : /* Ideally we'd print p->m_model here; see the notes above about
4882 : tooltips. */
4883 : }
4884 4 : pp_printf (pp, "</TABLE>");
4885 4 : gv->end_tdtr ();
4886 4 : }
4887 :
4888 : const exploded_graph &m_eg;
4889 : std::vector<std::vector <exploded_node *> > m_enodes_per_snode_id;
4890 : };
4891 :
4892 : /* Implement -fdump-analyzer-json. */
4893 :
4894 : static void
4895 0 : dump_analyzer_json (const supergraph &sg,
4896 : const exploded_graph &eg)
4897 : {
4898 0 : auto_timevar tv (TV_ANALYZER_DUMP);
4899 0 : char *filename = concat (dump_base_name, ".analyzer.json.gz", nullptr);
4900 0 : gzFile output = gzopen (filename, "w");
4901 0 : if (!output)
4902 : {
4903 0 : error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
4904 0 : free (filename);
4905 0 : return;
4906 : }
4907 :
4908 0 : auto toplev_obj = std::make_unique<json::object> ();
4909 0 : toplev_obj->set ("sgraph", sg.to_json ());
4910 0 : toplev_obj->set ("egraph", eg.to_json ());
4911 :
4912 0 : pretty_printer pp;
4913 0 : toplev_obj->print (&pp, flag_diagnostics_json_formatting);
4914 0 : pp_formatted_text (&pp);
4915 :
4916 0 : if (gzputs (output, pp_formatted_text (&pp)) == EOF
4917 0 : || gzclose (output))
4918 0 : error_at (UNKNOWN_LOCATION, "error writing %qs", filename);
4919 :
4920 0 : free (filename);
4921 0 : }
4922 :
4923 : /* Concrete subclass of on_ana_init, allowing plugins to register
4924 : new state machines. */
4925 :
4926 : class impl_on_ana_init : public gcc::topics::analyzer_events::on_ana_init
4927 : {
4928 : public:
4929 38 : impl_on_ana_init (std::vector<std::unique_ptr<state_machine>> &checkers,
4930 : known_function_manager &known_fn_mgr,
4931 : logger *logger)
4932 38 : : m_checkers (checkers),
4933 38 : m_known_fn_mgr (known_fn_mgr),
4934 38 : m_logger (logger)
4935 : {}
4936 :
4937 : void
4938 1 : register_state_machine (std::unique_ptr<state_machine> sm)
4939 : const final override
4940 : {
4941 1 : LOG_SCOPE (m_logger);
4942 1 : m_checkers.push_back (std::move (sm));
4943 1 : }
4944 :
4945 : void
4946 107 : register_known_function (const char *name,
4947 : std::unique_ptr<known_function> kf)
4948 : const final override
4949 : {
4950 107 : LOG_SCOPE (m_logger);
4951 107 : m_known_fn_mgr.add (name, std::move (kf));
4952 107 : }
4953 :
4954 : logger *
4955 38 : get_logger () const final override
4956 : {
4957 38 : return m_logger;
4958 : }
4959 :
4960 : private:
4961 : std::vector<std::unique_ptr<state_machine>> &m_checkers;
4962 : known_function_manager &m_known_fn_mgr;
4963 : logger *m_logger;
4964 : };
4965 :
4966 : static void
4967 14296 : maybe_dump_supergraph (const supergraph &sg, const char *name,
4968 : const dot_annotator *annotator = nullptr,
4969 : const exploded_graph *eg = nullptr)
4970 : {
4971 14296 : static int dump_idx = 0;
4972 14296 : if (!flag_dump_analyzer_supergraph)
4973 14276 : return;
4974 :
4975 20 : auto_timevar tv (TV_ANALYZER_DUMP);
4976 20 : std::string filename (dump_base_name);
4977 20 : filename += ".supergraph.";
4978 40 : filename += std::to_string (dump_idx++);
4979 20 : filename += ".";
4980 20 : filename += name;
4981 20 : filename += ".dot";
4982 20 : supergraph::dump_args_t args
4983 : ((enum supergraph_dot_flags)SUPERGRAPH_DOT_SHOW_BBS,
4984 : annotator,
4985 20 : eg);
4986 20 : sg.dump_dot (filename.c_str (), args);
4987 20 : }
4988 :
4989 : /* Run the analysis "engine". */
4990 :
4991 : void
4992 3573 : impl_run_checkers (logger *logger)
4993 : {
4994 3573 : LOG_SCOPE (logger);
4995 :
4996 3573 : if (logger)
4997 : {
4998 5 : logger->log ("BITS_BIG_ENDIAN: %i", BITS_BIG_ENDIAN ? 1 : 0);
4999 5 : logger->log ("BYTES_BIG_ENDIAN: %i", BYTES_BIG_ENDIAN ? 1 : 0);
5000 5 : logger->log ("WORDS_BIG_ENDIAN: %i", WORDS_BIG_ENDIAN ? 1 : 0);
5001 5 : log_stashed_constants (logger);
5002 : }
5003 :
5004 : /* If using LTO, ensure that the cgraph nodes have function bodies. */
5005 3573 : cgraph_node *node;
5006 15234 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
5007 11661 : node->get_untransformed_body ();
5008 :
5009 3573 : symbolic::node_manager node_mgr;
5010 3573 : auto &mgr = node_mgr.get_region_model_manager ();
5011 :
5012 : /* Create the supergraph. */
5013 3573 : supergraph sg (mgr, logger);
5014 :
5015 3573 : maybe_dump_supergraph (sg, "original");
5016 :
5017 3573 : sg.fixup_locations (logger);
5018 :
5019 3573 : maybe_dump_supergraph (sg, "fixup-locations");
5020 :
5021 3573 : engine eng (node_mgr, &sg);
5022 :
5023 3573 : state_purge_map *purge_map = nullptr;
5024 3573 : if (flag_analyzer_state_purge)
5025 3562 : purge_map = new state_purge_map (sg, eng.get_model_manager (), logger);
5026 :
5027 3573 : if (flag_analyzer_simplify_supergraph)
5028 : {
5029 3573 : sg.simplify (logger);
5030 3573 : maybe_dump_supergraph (sg, "simplified");
5031 : }
5032 :
5033 3573 : sg.sort_nodes (logger);
5034 3573 : maybe_dump_supergraph (sg, "sorted");
5035 :
5036 3573 : if (flag_dump_analyzer_state_purge)
5037 : {
5038 4 : auto_timevar tv (TV_ANALYZER_DUMP);
5039 4 : state_purge_annotator a (purge_map);
5040 4 : char *filename = concat (dump_base_name, ".state-purge.dot", nullptr);
5041 4 : supergraph::dump_args_t args ((enum supergraph_dot_flags)0, &a, nullptr);
5042 4 : sg.dump_dot (filename, args);
5043 4 : free (filename);
5044 4 : }
5045 :
5046 3573 : auto checkers = make_checkers (logger);
5047 :
5048 3573 : register_known_functions (*eng.get_known_function_manager (),
5049 3573 : *eng.get_model_manager ());
5050 :
5051 3573 : if (auto channel
5052 3573 : = g->get_channels ().analyzer_events_channel.get_if_active ())
5053 38 : channel->publish (impl_on_ana_init (checkers,
5054 38 : *eng.get_known_function_manager (),
5055 38 : logger));
5056 :
5057 3573 : if (logger)
5058 : {
5059 5 : int i = 0;
5060 40 : for (auto &sm : checkers)
5061 35 : logger->log ("checkers[%i]: %s", ++i, sm->get_name ());
5062 : }
5063 :
5064 : /* Extrinsic state shared by nodes in the graph. */
5065 3573 : const extrinsic_state ext_state (std::move (checkers), &eng, logger);
5066 :
5067 3573 : const analysis_plan plan (sg, logger);
5068 :
5069 : /* The exploded graph. */
5070 3573 : exploded_graph eg (sg, logger, ext_state, purge_map, plan,
5071 3573 : analyzer_verbosity);
5072 :
5073 : /* Add entrypoints to the graph for externally-callable functions. */
5074 3573 : eg.build_initial_worklist ();
5075 :
5076 : /* Now process the worklist, exploring the <point, state> graph. */
5077 3573 : eg.process_worklist ();
5078 :
5079 3573 : if (warn_analyzer_infinite_loop)
5080 3573 : eg.detect_infinite_loops ();
5081 :
5082 3573 : if (flag_dump_analyzer_exploded_graph)
5083 : {
5084 4 : auto_timevar tv (TV_ANALYZER_DUMP);
5085 4 : char *filename
5086 4 : = concat (dump_base_name, ".eg.dot", nullptr);
5087 4 : exploded_graph::dump_args_t args (eg);
5088 4 : root_cluster c;
5089 4 : eg.dump_dot (filename, &c, args);
5090 4 : free (filename);
5091 4 : }
5092 :
5093 : /* Now emit any saved diagnostics. */
5094 3573 : eg.get_diagnostic_manager ().emit_saved_diagnostics (eg);
5095 :
5096 3573 : eg.dump_exploded_nodes ();
5097 :
5098 3573 : eg.log_stats ();
5099 :
5100 3573 : if (flag_dump_analyzer_supergraph)
5101 : {
5102 : /* Dump post-analysis form of supergraph. */
5103 4 : exploded_graph_annotator a (eg);
5104 4 : maybe_dump_supergraph (sg, "eg", &a, &eg);
5105 4 : }
5106 :
5107 3573 : if (flag_dump_analyzer_json)
5108 0 : dump_analyzer_json (sg, eg);
5109 :
5110 3573 : if (flag_dump_analyzer_untracked)
5111 23 : eng.get_model_manager ()->dump_untracked_regions ();
5112 :
5113 3573 : if (auto channel
5114 3573 : = g->get_channels ().analyzer_events_channel.get_if_active ())
5115 38 : channel->publish (gcc::topics::analyzer_events::on_ana_done {eng, eg});
5116 :
5117 3573 : delete purge_map;
5118 :
5119 : /* Free up any dominance info that we may have created. */
5120 15234 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
5121 : {
5122 11661 : function *fun = node->get_fun ();
5123 11661 : free_dominance_info (fun, CDI_DOMINATORS);
5124 : }
5125 3573 : }
5126 :
5127 : /* Handle -fdump-analyzer and -fdump-analyzer-stderr. */
5128 : static FILE *dump_fout = nullptr;
5129 :
5130 : /* Track if we're responsible for closing dump_fout. */
5131 : static bool owns_dump_fout = false;
5132 :
5133 : /* If dumping is enabled, attempt to create dump_fout if it hasn't already
5134 : been opened. Return it. */
5135 :
5136 : FILE *
5137 7189 : get_or_create_any_logfile ()
5138 : {
5139 7189 : if (!dump_fout)
5140 : {
5141 7184 : if (flag_dump_analyzer_stderr)
5142 0 : dump_fout = stderr;
5143 7184 : else if (flag_dump_analyzer)
5144 : {
5145 5 : char *dump_filename = concat (dump_base_name, ".analyzer.txt", nullptr);
5146 5 : dump_fout = fopen (dump_filename, "w");
5147 5 : free (dump_filename);
5148 5 : if (dump_fout)
5149 5 : owns_dump_fout = true;
5150 : }
5151 : }
5152 7189 : return dump_fout;
5153 : }
5154 :
5155 : /* External entrypoint to the analysis "engine".
5156 : Set up any dumps, then call impl_run_checkers. */
5157 :
5158 : void
5159 3573 : run_checkers ()
5160 : {
5161 : /* Save input_location. */
5162 3573 : location_t saved_input_location = input_location;
5163 :
5164 3573 : {
5165 3573 : log_user the_logger (nullptr);
5166 3573 : get_or_create_any_logfile ();
5167 3573 : if (dump_fout)
5168 5 : the_logger.set_logger (new logger (dump_fout, 0, 0,
5169 5 : *global_dc->get_reference_printer ()));
5170 3573 : LOG_SCOPE (the_logger.get_logger ());
5171 :
5172 3573 : impl_run_checkers (the_logger.get_logger ());
5173 :
5174 : /* end of lifetime of the_logger (so that dump file is closed after the
5175 : various dtors run). */
5176 3573 : }
5177 :
5178 3573 : if (owns_dump_fout)
5179 : {
5180 5 : fclose (dump_fout);
5181 5 : owns_dump_fout = false;
5182 5 : dump_fout = nullptr;
5183 : }
5184 :
5185 : /* Restore input_location. Subsequent passes may assume that input_location
5186 : is some arbitrary value *not* in the block tree, which might be violated
5187 : if we didn't restore it. */
5188 3573 : input_location = saved_input_location;
5189 3573 : }
5190 :
5191 : } // namespace ana
5192 :
5193 : #endif /* #if ENABLE_ANALYZER */
|