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