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