1 /* The analysis "engine".
2 Copyright (C) 2019-2022 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
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)
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.
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/>. */
22 #define INCLUDE_MEMORY
24 #include "coretypes.h"
25 #include "make-unique.h"
27 #include "fold-const.h"
28 #include "gcc-rich-location.h"
29 #include "diagnostic-core.h"
30 #include "diagnostic-event-id.h"
31 #include "diagnostic-path.h"
33 #include "pretty-print.h"
36 #include "ordered-hash-map.h"
37 #include "analyzer/analyzer.h"
38 #include "analyzer/analyzer-logging.h"
39 #include "analyzer/call-string.h"
40 #include "analyzer/program-point.h"
41 #include "analyzer/store.h"
42 #include "analyzer/region-model.h"
43 #include "analyzer/constraint-manager.h"
44 #include "analyzer/sm.h"
45 #include "analyzer/pending-diagnostic.h"
46 #include "analyzer/diagnostic-manager.h"
48 #include "basic-block.h"
50 #include "gimple-iterator.h"
51 #include "gimple-pretty-print.h"
54 #include "analyzer/supergraph.h"
55 #include "analyzer/program-state.h"
56 #include "analyzer/exploded-graph.h"
57 #include "analyzer/analysis-plan.h"
58 #include "analyzer/checker-path.h"
59 #include "analyzer/state-purge.h"
60 #include "analyzer/bar-chart.h"
61 #include "analyzer/call-info.h"
66 #include "stringpool.h"
69 #include "analyzer/known-function-manager.h"
70 #include "analyzer/call-summary.h"
72 /* For an overview, see gcc/doc/analyzer.texi. */
78 /* class impl_region_model_context : public region_model_context. */
80 impl_region_model_context::
81 impl_region_model_context (exploded_graph &eg,
82 exploded_node *enode_for_diag,
83 const program_state *old_state,
84 program_state *new_state,
85 uncertainty_t *uncertainty,
86 path_context *path_ctxt,
88 stmt_finder *stmt_finder)
89 : m_eg (&eg), m_logger (eg.get_logger ()),
90 m_enode_for_diag (enode_for_diag),
91 m_old_state (old_state),
92 m_new_state (new_state),
94 m_stmt_finder (stmt_finder),
95 m_ext_state (eg.get_ext_state ()),
96 m_uncertainty (uncertainty),
97 m_path_ctxt (path_ctxt)
101 impl_region_model_context::
102 impl_region_model_context (program_state *state,
103 const extrinsic_state &ext_state,
104 uncertainty_t *uncertainty,
106 : m_eg (NULL), m_logger (logger), m_enode_for_diag (NULL),
110 m_stmt_finder (NULL),
111 m_ext_state (ext_state),
112 m_uncertainty (uncertainty),
118 impl_region_model_context::warn (std::unique_ptr<pending_diagnostic> d)
120 LOG_FUNC (get_logger ());
121 if (m_stmt == NULL && m_stmt_finder == NULL)
124 get_logger ()->log ("rejecting diagnostic: no stmt");
128 return m_eg->get_diagnostic_manager ().add_diagnostic
129 (m_enode_for_diag, m_enode_for_diag->get_supernode (),
130 m_stmt, m_stmt_finder, std::move (d));
136 impl_region_model_context::add_note (std::unique_ptr<pending_note> pn)
138 LOG_FUNC (get_logger ());
140 m_eg->get_diagnostic_manager ().add_note (std::move (pn));
144 impl_region_model_context::on_svalue_leak (const svalue *sval)
147 for (sm_state_map *smap : m_new_state->m_checker_states)
148 smap->on_svalue_leak (sval, this);
152 impl_region_model_context::
153 on_liveness_change (const svalue_set &live_svalues,
154 const region_model *model)
156 for (sm_state_map *smap : m_new_state->m_checker_states)
157 smap->on_liveness_change (live_svalues, model, this);
161 impl_region_model_context::on_unknown_change (const svalue *sval,
164 if (!sval->can_have_associated_state_p ())
166 for (sm_state_map *smap : m_new_state->m_checker_states)
167 smap->on_unknown_change (sval, is_mutable, m_ext_state);
171 impl_region_model_context::on_escaped_function (tree fndecl)
173 m_eg->on_escaped_function (fndecl);
177 impl_region_model_context::get_uncertainty ()
179 return m_uncertainty;
182 /* Purge state involving SVAL. The region_model has already been purged,
183 so we only need to purge other state in the program_state:
187 impl_region_model_context::purge_state_involving (const svalue *sval)
191 FOR_EACH_VEC_ELT (m_new_state->m_checker_states, i, smap)
192 smap->purge_state_involving (sval, m_ext_state);
196 impl_region_model_context::bifurcate (std::unique_ptr<custom_edge_info> info)
199 m_path_ctxt->bifurcate (std::move (info));
203 impl_region_model_context::terminate_path ()
206 return m_path_ctxt->terminate_path ();
209 /* struct setjmp_record. */
212 setjmp_record::cmp (const setjmp_record &rec1, const setjmp_record &rec2)
214 if (int cmp_enode = rec1.m_enode->m_index - rec2.m_enode->m_index)
216 gcc_assert (&rec1 == &rec2);
220 /* class setjmp_svalue : public svalue. */
222 /* Implementation of svalue::accept vfunc for setjmp_svalue. */
225 setjmp_svalue::accept (visitor *v) const
227 v->visit_setjmp_svalue (this);
230 /* Implementation of svalue::dump_to_pp vfunc for setjmp_svalue. */
233 setjmp_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
236 pp_printf (pp, "SETJMP(EN: %i)", get_enode_index ());
238 pp_printf (pp, "setjmp_svalue(EN%i)", get_enode_index ());
241 /* Get the index of the stored exploded_node. */
244 setjmp_svalue::get_enode_index () const
246 return m_setjmp_record.m_enode->m_index;
249 /* Concrete implementation of sm_context, wiring it up to the rest of this
252 class impl_sm_context : public sm_context
255 impl_sm_context (exploded_graph &eg,
257 const state_machine &sm,
258 exploded_node *enode_for_diag,
259 const program_state *old_state,
260 program_state *new_state,
261 const sm_state_map *old_smap,
262 sm_state_map *new_smap,
263 path_context *path_ctxt,
264 const stmt_finder *stmt_finder = NULL,
265 bool unknown_side_effects = false)
266 : sm_context (sm_idx, sm),
267 m_logger (eg.get_logger ()),
268 m_eg (eg), m_enode_for_diag (enode_for_diag),
269 m_old_state (old_state), m_new_state (new_state),
270 m_old_smap (old_smap), m_new_smap (new_smap),
271 m_path_ctxt (path_ctxt),
272 m_stmt_finder (stmt_finder),
273 m_unknown_side_effects (unknown_side_effects)
277 logger *get_logger () const { return m_logger.get_logger (); }
279 tree get_fndecl_for_call (const gcall *call) final override
281 impl_region_model_context old_ctxt
282 (m_eg, m_enode_for_diag, NULL, NULL, NULL/*m_enode->get_state ()*/,
284 region_model *model = m_new_state->m_region_model;
285 return model->get_fndecl_for_call (call, &old_ctxt);
288 state_machine::state_t get_state (const gimple *stmt ATTRIBUTE_UNUSED,
289 tree var) final override
291 logger * const logger = get_logger ();
293 /* Use NULL ctxt on this get_rvalue call to avoid triggering
294 uninitialized value warnings. */
295 const svalue *var_old_sval
296 = m_old_state->m_region_model->get_rvalue (var, NULL);
298 state_machine::state_t current
299 = m_old_smap->get_state (var_old_sval, m_eg.get_ext_state ());
302 state_machine::state_t get_state (const gimple *stmt ATTRIBUTE_UNUSED,
303 const svalue *sval) final override
305 logger * const logger = get_logger ();
307 state_machine::state_t current
308 = m_old_smap->get_state (sval, m_eg.get_ext_state ());
313 void set_next_state (const gimple *,
315 state_machine::state_t to,
316 tree origin) final override
318 logger * const logger = get_logger ();
320 const svalue *var_new_sval
321 = m_new_state->m_region_model->get_rvalue (var, NULL);
322 const svalue *origin_new_sval
323 = m_new_state->m_region_model->get_rvalue (origin, NULL);
325 /* We use the new sval here to avoid issues with uninitialized values. */
326 state_machine::state_t current
327 = m_old_smap->get_state (var_new_sval, m_eg.get_ext_state ());
329 logger->log ("%s: state transition of %qE: %s -> %s",
332 current->get_name (),
334 m_new_smap->set_state (m_new_state->m_region_model, var_new_sval,
335 to, origin_new_sval, m_eg.get_ext_state ());
338 void set_next_state (const gimple *stmt,
340 state_machine::state_t to,
341 tree origin) final override
343 logger * const logger = get_logger ();
345 impl_region_model_context old_ctxt
346 (m_eg, m_enode_for_diag, NULL, NULL, NULL/*m_enode->get_state ()*/,
349 const svalue *origin_new_sval
350 = m_new_state->m_region_model->get_rvalue (origin, NULL);
352 state_machine::state_t current
353 = m_old_smap->get_state (sval, m_eg.get_ext_state ());
356 logger->start_log_line ();
357 logger->log_partial ("%s: state transition of ",
359 sval->dump_to_pp (logger->get_printer (), true);
360 logger->log_partial (": %s -> %s",
361 current->get_name (),
363 logger->end_log_line ();
365 m_new_smap->set_state (m_new_state->m_region_model, sval,
366 to, origin_new_sval, m_eg.get_ext_state ());
369 void warn (const supernode *snode, const gimple *stmt,
371 std::unique_ptr<pending_diagnostic> d) final override
373 LOG_FUNC (get_logger ());
375 const svalue *var_old_sval
376 = m_old_state->m_region_model->get_rvalue (var, NULL);
377 state_machine::state_t current
379 ? m_old_smap->get_state (var_old_sval, m_eg.get_ext_state ())
380 : m_old_smap->get_global_state ());
381 m_eg.get_diagnostic_manager ().add_diagnostic
382 (&m_sm, m_enode_for_diag, snode, stmt, m_stmt_finder,
383 var, var_old_sval, current, std::move (d));
386 void warn (const supernode *snode, const gimple *stmt,
388 std::unique_ptr<pending_diagnostic> d) final override
390 LOG_FUNC (get_logger ());
392 state_machine::state_t current
394 ? m_old_smap->get_state (sval, m_eg.get_ext_state ())
395 : m_old_smap->get_global_state ());
396 m_eg.get_diagnostic_manager ().add_diagnostic
397 (&m_sm, m_enode_for_diag, snode, stmt, m_stmt_finder,
398 NULL_TREE, sval, current, std::move (d));
401 /* Hook for picking more readable trees for SSA names of temporaries,
402 so that rather than e.g.
403 "double-free of '<unknown>'"
405 "double-free of 'inbuf.data'". */
407 tree get_diagnostic_tree (tree expr) final override
409 /* Only for SSA_NAMEs of temporaries; otherwise, return EXPR, as it's
410 likely to be the least surprising tree to report. */
411 if (TREE_CODE (expr) != SSA_NAME)
413 if (SSA_NAME_VAR (expr) != NULL)
416 gcc_assert (m_new_state);
417 const svalue *sval = m_new_state->m_region_model->get_rvalue (expr, NULL);
418 /* Find trees for all regions storing the value. */
419 if (tree t = m_new_state->m_region_model->get_representative_tree (sval))
425 tree get_diagnostic_tree (const svalue *sval) final override
427 return m_new_state->m_region_model->get_representative_tree (sval);
430 state_machine::state_t get_global_state () const final override
432 return m_old_state->m_checker_states[m_sm_idx]->get_global_state ();
435 void set_global_state (state_machine::state_t state) final override
437 m_new_state->m_checker_states[m_sm_idx]->set_global_state (state);
440 void on_custom_transition (custom_transition *transition) final override
442 transition->impl_transition (&m_eg,
443 const_cast<exploded_node *> (m_enode_for_diag),
447 tree is_zero_assignment (const gimple *stmt) final override
449 const gassign *assign_stmt = dyn_cast <const gassign *> (stmt);
452 impl_region_model_context old_ctxt
453 (m_eg, m_enode_for_diag, m_old_state, m_new_state, NULL, NULL, stmt);
454 if (const svalue *sval
455 = m_new_state->m_region_model->get_gassign_result (assign_stmt,
457 if (tree cst = sval->maybe_get_constant ())
459 return gimple_assign_lhs (assign_stmt);
463 path_context *get_path_context () const final override
468 bool unknown_side_effects_p () const final override
470 return m_unknown_side_effects;
473 const program_state *get_old_program_state () const final override
478 const program_state *get_new_program_state () const final override
484 exploded_graph &m_eg;
485 exploded_node *m_enode_for_diag;
486 const program_state *m_old_state;
487 program_state *m_new_state;
488 const sm_state_map *m_old_smap;
489 sm_state_map *m_new_smap;
490 path_context *m_path_ctxt;
491 const stmt_finder *m_stmt_finder;
493 /* Are we handling an external function with unknown side effects? */
494 bool m_unknown_side_effects;
498 impl_region_model_context::
499 get_state_map_by_name (const char *name,
500 sm_state_map **out_smap,
501 const state_machine **out_sm,
502 unsigned *out_sm_idx,
503 std::unique_ptr<sm_context> *out_sm_context)
509 if (!m_ext_state.get_sm_idx_by_name (name, &sm_idx))
512 const state_machine *sm = &m_ext_state.get_sm (sm_idx);
513 sm_state_map *new_smap = m_new_state->m_checker_states[sm_idx];
515 *out_smap = new_smap;
518 *out_sm_idx = sm_idx;
521 const sm_state_map *old_smap = m_old_state->m_checker_states[sm_idx];
523 = make_unique<impl_sm_context> (*m_eg,
538 /* Subclass of stmt_finder for finding the best stmt to report the leak at,
539 given the emission path. */
541 class leak_stmt_finder : public stmt_finder
544 leak_stmt_finder (const exploded_graph &eg, tree var)
545 : m_eg (eg), m_var (var) {}
547 std::unique_ptr<stmt_finder> clone () const final override
549 return make_unique<leak_stmt_finder> (m_eg, m_var);
552 const gimple *find_stmt (const exploded_path &epath)
555 logger * const logger = m_eg.get_logger ();
558 if (m_var && TREE_CODE (m_var) == SSA_NAME)
560 /* Locate the final write to this SSA name in the path. */
561 const gimple *def_stmt = SSA_NAME_DEF_STMT (m_var);
564 bool found = epath.find_stmt_backwards (def_stmt, &idx_of_def_stmt);
568 /* What was the next write to the underlying var
569 after the SSA name was set? (if any). */
571 for (unsigned idx = idx_of_def_stmt + 1;
572 idx < epath.m_edges.length ();
575 const exploded_edge *eedge = epath.m_edges[idx];
577 logger->log ("eedge[%i]: EN %i -> EN %i",
579 eedge->m_src->m_index,
580 eedge->m_dest->m_index);
581 const exploded_node *dst_node = eedge->m_dest;
582 const program_point &dst_point = dst_node->get_point ();
583 const gimple *stmt = dst_point.get_stmt ();
586 if (const gassign *assign = dyn_cast <const gassign *> (stmt))
588 tree lhs = gimple_assign_lhs (assign);
589 if (TREE_CODE (lhs) == SSA_NAME
590 && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (m_var))
598 /* Look backwards for the first statement with a location. */
600 const exploded_edge *eedge;
601 FOR_EACH_VEC_ELT_REVERSE (epath.m_edges, i, eedge)
604 logger->log ("eedge[%i]: EN %i -> EN %i",
606 eedge->m_src->m_index,
607 eedge->m_dest->m_index);
608 const exploded_node *dst_node = eedge->m_dest;
609 const program_point &dst_point = dst_node->get_point ();
610 const gimple *stmt = dst_point.get_stmt ();
612 if (get_pure_location (stmt->location) != UNKNOWN_LOCATION)
621 const exploded_graph &m_eg;
625 /* A measurement of how good EXPR is for presenting to the user, so
626 that e.g. we can say prefer printing
627 "leak of 'tmp.m_ptr'"
629 "leak of '<unknown>'". */
632 readability (const_tree expr)
634 /* Arbitrarily-chosen "high readability" value. */
635 const int HIGH_READABILITY = 65536;
638 switch (TREE_CODE (expr))
642 /* Impose a slight readability penalty relative to that of
644 return readability (TREE_OPERAND (expr, 0)) - 16;
648 if (tree var = SSA_NAME_VAR (expr))
650 if (DECL_ARTIFICIAL (var))
652 /* If we have an SSA name for an artificial var,
653 only use it if it has a debug expr associated with
654 it that fixup_tree_for_diagnostic can use. */
655 if (VAR_P (var) && DECL_HAS_DEBUG_EXPR_P (var))
656 return readability (DECL_DEBUG_EXPR (var)) - 1;
660 /* Slightly favor the underlying var over the SSA name to
661 avoid having them compare equal. */
662 return readability (var) - 1;
665 /* Avoid printing '<unknown>' for SSA names for temporaries. */
672 if (DECL_NAME (expr))
673 return HIGH_READABILITY;
675 /* We don't want to print temporaries. For example, the C FE
676 prints them as e.g. "<Uxxxx>" where "xxxx" is the low 16 bits
677 of the tree pointer (see pp_c_tree_decl_identifier). */
681 /* Printing "<return-value>" isn't ideal, but is less awful than
682 trying to print a temporary. */
683 return HIGH_READABILITY / 2;
687 /* Impose a moderate readability penalty for casts. */
688 const int CAST_PENALTY = 32;
689 return readability (TREE_OPERAND (expr, 0)) - CAST_PENALTY;
693 return HIGH_READABILITY;
702 /* A qsort comparator for trees to sort them into most user-readable to
703 least user-readable. */
706 readability_comparator (const void *p1, const void *p2)
708 path_var pv1 = *(path_var const *)p1;
709 path_var pv2 = *(path_var const *)p2;
711 const int tree_r1 = readability (pv1.m_tree);
712 const int tree_r2 = readability (pv2.m_tree);
714 /* Favor items that are deeper on the stack and hence more recent;
715 this also favors locals over globals. */
716 const int COST_PER_FRAME = 64;
717 const int depth_r1 = pv1.m_stack_depth * COST_PER_FRAME;
718 const int depth_r2 = pv2.m_stack_depth * COST_PER_FRAME;
720 /* Combine the scores from the tree and from the stack depth.
721 This e.g. lets us have a slightly penalized cast in the most
722 recent stack frame "beat" an uncast value in an older stack frame. */
723 const int sum_r1 = tree_r1 + depth_r1;
724 const int sum_r2 = tree_r2 + depth_r2;
725 if (int cmp = sum_r2 - sum_r1)
728 /* Otherwise, more readable trees win. */
729 if (int cmp = tree_r2 - tree_r1)
732 /* Otherwise, if they have the same readability, then impose an
733 arbitrary deterministic ordering on them. */
735 if (int cmp = TREE_CODE (pv1.m_tree) - TREE_CODE (pv2.m_tree))
738 switch (TREE_CODE (pv1.m_tree))
743 if (int cmp = (SSA_NAME_VERSION (pv1.m_tree)
744 - SSA_NAME_VERSION (pv2.m_tree)))
750 if (int cmp = DECL_UID (pv1.m_tree) - DECL_UID (pv2.m_tree))
755 /* TODO: We ought to find ways of sorting such cases. */
759 /* Return true is SNODE is the EXIT node of a function, or is one
760 of the final snodes within its function.
762 Specifically, handle the final supernodes before the EXIT node,
763 for the case of clobbers that happen immediately before exiting.
764 We need a run of snodes leading to the return_p snode, where all edges are
765 intraprocedural, and every snode has just one successor.
767 We use this when suppressing leak reports at the end of "main". */
770 returning_from_function_p (const supernode *snode)
776 const supernode *iter = snode;
779 if (iter->return_p ())
781 if (iter->m_succs.length () != 1)
783 const superedge *sedge = iter->m_succs[0];
784 if (sedge->get_kind () != SUPEREDGE_CFG_EDGE)
786 iter = sedge->m_dest;
788 /* Impose a limit to ensure we terminate for pathological cases.
790 We only care about the final 3 nodes, due to cases like:
792 (clobber causing leak)
804 /* Find the best tree for SVAL and call SM's on_leak vfunc with it.
805 If on_leak returns a pending_diagnostic, queue it up to be reported,
806 so that we potentially complain about a leak of SVAL in the given STATE. */
809 impl_region_model_context::on_state_leak (const state_machine &sm,
811 state_machine::state_t state)
813 logger * const logger = get_logger ();
817 logger->start_log_line ();
818 logger->log_partial ("considering leak of ");
819 sval->dump_to_pp (logger->get_printer (), true);
820 logger->end_log_line ();
826 /* m_old_state also needs to be non-NULL so that the sm_ctxt can look
827 up the old state of SVAL. */
828 gcc_assert (m_old_state);
830 /* SVAL has leaked within the new state: it is not used by any reachable
832 We need to convert it back to a tree, but since it's likely no regions
833 use it, we have to find the "best" tree for it in the old_state. */
836 = m_old_state->m_region_model->get_representative_path_var (sval,
839 /* Strip off top-level casts */
840 if (leaked_pv.m_tree && TREE_CODE (leaked_pv.m_tree) == NOP_EXPR)
841 leaked_pv.m_tree = TREE_OPERAND (leaked_pv.m_tree, 0);
843 /* This might be NULL; the pending_diagnostic subclasses need to cope
845 tree leaked_tree = leaked_pv.m_tree;
849 logger->log ("best leaked_tree: %qE", leaked_tree);
851 logger->log ("best leaked_tree: NULL");
854 leak_stmt_finder stmt_finder (*m_eg, leaked_tree);
855 gcc_assert (m_enode_for_diag);
857 /* Don't complain about leaks when returning from "main". */
858 if (returning_from_function_p (m_enode_for_diag->get_supernode ()))
860 tree fndecl = m_enode_for_diag->get_function ()->decl;
861 if (id_equal (DECL_NAME (fndecl), "main"))
864 logger->log ("not reporting leak from main");
869 tree leaked_tree_for_diag = fixup_tree_for_diagnostic (leaked_tree);
870 std::unique_ptr<pending_diagnostic> pd = sm.on_leak (leaked_tree_for_diag);
872 m_eg->get_diagnostic_manager ().add_diagnostic
873 (&sm, m_enode_for_diag, m_enode_for_diag->get_supernode (),
874 m_stmt, &stmt_finder,
875 leaked_tree_for_diag, sval, state, std::move (pd));
878 /* Implementation of region_model_context::on_condition vfunc.
879 Notify all state machines about the condition, which could lead to
880 state transitions. */
883 impl_region_model_context::on_condition (const svalue *lhs,
889 FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
891 const state_machine &sm = m_ext_state.get_sm (sm_idx);
892 impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
893 m_old_state, m_new_state,
894 m_old_state->m_checker_states[sm_idx],
895 m_new_state->m_checker_states[sm_idx],
897 sm.on_condition (&sm_ctxt,
899 ? m_enode_for_diag->get_supernode ()
906 /* Implementation of region_model_context::on_bounded_ranges vfunc.
907 Notify all state machines about the ranges, which could lead to
908 state transitions. */
911 impl_region_model_context::on_bounded_ranges (const svalue &sval,
912 const bounded_ranges &ranges)
916 FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
918 const state_machine &sm = m_ext_state.get_sm (sm_idx);
919 impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
920 m_old_state, m_new_state,
921 m_old_state->m_checker_states[sm_idx],
922 m_new_state->m_checker_states[sm_idx],
924 sm.on_bounded_ranges (&sm_ctxt,
926 ? m_enode_for_diag->get_supernode ()
928 m_stmt, sval, ranges);
932 /* Implementation of region_model_context::on_pop_frame vfunc.
933 Notify all state machines about the frame being popped, which
934 could lead to states being discarded. */
937 impl_region_model_context::on_pop_frame (const frame_region *frame_reg)
941 FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
943 const state_machine &sm = m_ext_state.get_sm (sm_idx);
944 sm.on_pop_frame (smap, frame_reg);
948 /* Implementation of region_model_context::on_phi vfunc.
949 Notify all state machines about the phi, which could lead to
950 state transitions. */
953 impl_region_model_context::on_phi (const gphi *phi, tree rhs)
957 FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
959 const state_machine &sm = m_ext_state.get_sm (sm_idx);
960 impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
961 m_old_state, m_new_state,
962 m_old_state->m_checker_states[sm_idx],
963 m_new_state->m_checker_states[sm_idx],
965 sm.on_phi (&sm_ctxt, m_enode_for_diag->get_supernode (), phi, rhs);
969 /* Implementation of region_model_context::on_unexpected_tree_code vfunc.
970 Mark the new state as being invalid for further exploration.
971 TODO(stage1): introduce a warning for when this occurs. */
974 impl_region_model_context::on_unexpected_tree_code (tree t,
975 const dump_location_t &loc)
977 logger * const logger = get_logger ();
979 logger->log ("unhandled tree code: %qs in %qs at %s:%i",
980 get_tree_code_name (TREE_CODE (t)),
981 loc.get_impl_location ().m_function,
982 loc.get_impl_location ().m_file,
983 loc.get_impl_location ().m_line);
985 m_new_state->m_valid = false;
988 /* struct point_and_state. */
990 /* Assert that this object is sane. */
993 point_and_state::validate (const extrinsic_state &ext_state) const
995 /* Skip this in a release build. */
1000 m_point.validate ();
1002 m_state.validate (ext_state);
1004 /* Verify that the callstring's model of the stack corresponds to that
1005 of the region_model. */
1006 /* They should have the same depth. */
1007 gcc_assert (m_point.get_stack_depth ()
1008 == m_state.m_region_model->get_stack_depth ());
1009 /* Check the functions in the callstring vs those in the frames
1011 for (const frame_region *iter_frame
1012 = m_state.m_region_model->get_current_frame ();
1013 iter_frame; iter_frame = iter_frame->get_calling_frame ())
1015 int index = iter_frame->get_index ();
1016 gcc_assert (m_point.get_function_at_depth (index)
1017 == iter_frame->get_function ());
1021 /* Subroutine of print_enode_indices: print a run of indices from START_IDX
1022 to END_IDX to PP, using and updating *FIRST_RUN. */
1025 print_run (pretty_printer *pp, int start_idx, int end_idx,
1029 pp_string (pp, ", ");
1031 if (start_idx == end_idx)
1032 pp_printf (pp, "EN: %i", start_idx);
1034 pp_printf (pp, "EN: %i-%i", start_idx, end_idx);
1037 /* Print the indices within ENODES to PP, collecting them as
1038 runs/singletons e.g. "EN: 4-7, EN: 20-23, EN: 42". */
1041 print_enode_indices (pretty_printer *pp,
1042 const auto_vec<exploded_node *> &enodes)
1044 int cur_start_idx = -1;
1045 int cur_finish_idx = -1;
1046 bool first_run = true;
1048 exploded_node *enode;
1049 FOR_EACH_VEC_ELT (enodes, i, enode)
1051 if (cur_start_idx == -1)
1053 gcc_assert (cur_finish_idx == -1);
1054 cur_start_idx = cur_finish_idx = enode->m_index;
1058 if (enode->m_index == cur_finish_idx + 1)
1059 /* Continuation of a run. */
1060 cur_finish_idx = enode->m_index;
1063 /* Finish existing run, start a new one. */
1064 gcc_assert (cur_start_idx >= 0);
1065 gcc_assert (cur_finish_idx >= 0);
1066 print_run (pp, cur_start_idx, cur_finish_idx,
1068 cur_start_idx = cur_finish_idx = enode->m_index;
1072 /* Finish any existing run. */
1073 if (cur_start_idx >= 0)
1075 gcc_assert (cur_finish_idx >= 0);
1076 print_run (pp, cur_start_idx, cur_finish_idx,
1081 /* struct eg_traits::dump_args_t. */
1083 /* The <FILENAME>.eg.dot output can quickly become unwieldy if we show
1084 full details for all enodes (both in terms of CPU time to render it,
1085 and in terms of being meaningful to a human viewing it).
1087 If we show just the IDs then the resulting graph is usually viewable,
1088 but then we have to keep switching back and forth between the .dot
1089 view and other dumps.
1091 This function implements a heuristic for showing detail at the enodes
1092 that (we hope) matter, and just the ID at other enodes, fixing the CPU
1093 usage of the .dot viewer, and drawing the attention of the viewer
1096 Return true if ENODE should be shown in detail in .dot output.
1097 Return false if no detail should be shown for ENODE. */
1100 eg_traits::dump_args_t::show_enode_details_p (const exploded_node &enode) const
1102 /* If the number of exploded nodes isn't too large, we may as well show
1103 all enodes in full detail in the .dot output. */
1104 if (m_eg.m_nodes.length ()
1105 <= (unsigned) param_analyzer_max_enodes_for_full_dump)
1108 /* Otherwise, assume that what's most interesting are state explosions,
1109 and thus the places where this happened.
1110 Expand enodes at program points where we hit the per-enode limit, so we
1111 can investigate what exploded. */
1112 const per_program_point_data *per_point_data
1113 = m_eg.get_per_program_point_data (enode.get_point ());
1114 return per_point_data->m_excess_enodes > 0;
1117 /* class exploded_node : public dnode<eg_traits>. */
1120 exploded_node::status_to_str (enum status s)
1124 default: gcc_unreachable ();
1125 case STATUS_WORKLIST: return "WORKLIST";
1126 case STATUS_PROCESSED: return "PROCESSED";
1127 case STATUS_MERGER: return "MERGER";
1128 case STATUS_BULK_MERGED: return "BULK_MERGED";
1132 /* exploded_node's ctor. */
1134 exploded_node::exploded_node (const point_and_state &ps,
1136 : m_ps (ps), m_status (STATUS_WORKLIST), m_index (index),
1137 m_num_processed_stmts (0)
1139 gcc_checking_assert (ps.get_state ().m_region_model->canonicalized_p ());
1142 /* Get the stmt that was processed in this enode at index IDX.
1143 IDX is an index within the stmts processed at this enode, rather
1144 than within those of the supernode. */
1147 exploded_node::get_processed_stmt (unsigned idx) const
1149 gcc_assert (idx < m_num_processed_stmts);
1150 const program_point &point = get_point ();
1151 gcc_assert (point.get_kind () == PK_BEFORE_STMT);
1152 const supernode *snode = get_supernode ();
1153 const unsigned int point_stmt_idx = point.get_stmt_idx ();
1154 const unsigned int idx_within_snode = point_stmt_idx + idx;
1155 const gimple *stmt = snode->m_stmts[idx_within_snode];
1159 /* For use by dump_dot, get a value for the .dot "fillcolor" attribute.
1160 Colorize by sm-state, to make it easier to see how sm-state propagates
1161 through the exploded_graph. */
1164 exploded_node::get_dot_fillcolor () const
1166 const program_state &state = get_state ();
1168 /* We want to be able to easily distinguish the no-sm-state case,
1169 and to be able to distinguish cases where there's a single state
1172 Sum the sm_states, and use the result to choose from a table,
1173 modulo table-size, special-casing the "no sm-state" case. */
1174 int total_sm_state = 0;
1177 FOR_EACH_VEC_ELT (state.m_checker_states, i, smap)
1179 for (sm_state_map::iterator_t iter = smap->begin ();
1180 iter != smap->end ();
1182 total_sm_state += (*iter).second.m_state->get_id ();
1183 total_sm_state += smap->get_global_state ()->get_id ();
1186 if (total_sm_state > 0)
1188 /* An arbitrarily-picked collection of light colors. */
1189 const char * const colors[]
1190 = {"azure", "coral", "cornsilk", "lightblue", "yellow",
1191 "honeydew", "lightpink", "lightsalmon", "palegreen1",
1192 "wheat", "seashell"};
1193 const int num_colors = ARRAY_SIZE (colors);
1194 return colors[total_sm_state % num_colors];
1201 /* Implementation of dnode::dump_dot vfunc for exploded_node. */
1204 exploded_node::dump_dot (graphviz_out *gv, const dump_args_t &args) const
1206 pretty_printer *pp = gv->get_pp ();
1209 pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
1210 get_dot_fillcolor ());
1211 pp_write_text_to_stream (pp);
1213 pp_printf (pp, "EN: %i", m_index);
1214 if (m_status == STATUS_MERGER)
1215 pp_string (pp, " (merger)");
1216 else if (m_status == STATUS_BULK_MERGED)
1217 pp_string (pp, " (bulk merged)");
1220 if (args.show_enode_details_p (*this))
1223 m_ps.get_point ().print (pp, f);
1226 const extrinsic_state &ext_state = args.m_eg.get_ext_state ();
1227 const program_state &state = m_ps.get_state ();
1228 state.dump_to_pp (ext_state, false, true, pp);
1231 dump_processed_stmts (pp);
1234 dump_saved_diagnostics (pp);
1236 args.dump_extra_info (this, pp);
1238 pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
1240 pp_string (pp, "\"];\n\n");
1242 /* It can be hard to locate the saved diagnostics as text within the
1243 enode nodes, so add extra nodes to the graph for each saved_diagnostic,
1245 Compare with dump_saved_diagnostics. */
1248 const saved_diagnostic *sd;
1249 FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
1251 sd->dump_as_dot_node (pp);
1253 /* Add edge connecting this enode to the saved_diagnostic. */
1255 pp_string (pp, " -> ");
1256 sd->dump_dot_id (pp);
1257 pp_string (pp, " [style=\"dotted\" arrowhead=\"none\"];");
1265 /* Show any stmts that were processed within this enode,
1266 and their index within the supernode. */
1268 exploded_node::dump_processed_stmts (pretty_printer *pp) const
1270 if (m_num_processed_stmts > 0)
1272 const program_point &point = get_point ();
1273 gcc_assert (point.get_kind () == PK_BEFORE_STMT);
1274 const supernode *snode = get_supernode ();
1275 const unsigned int point_stmt_idx = point.get_stmt_idx ();
1277 pp_printf (pp, "stmts: %i", m_num_processed_stmts);
1279 for (unsigned i = 0; i < m_num_processed_stmts; i++)
1281 const unsigned int idx_within_snode = point_stmt_idx + i;
1282 const gimple *stmt = snode->m_stmts[idx_within_snode];
1283 pp_printf (pp, " %i: ", idx_within_snode);
1284 pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
1290 /* Dump any saved_diagnostics at this enode to PP. */
1293 exploded_node::dump_saved_diagnostics (pretty_printer *pp) const
1296 const saved_diagnostic *sd;
1297 FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
1299 pp_printf (pp, "DIAGNOSTIC: %s (sd: %i)",
1300 sd->m_d->get_kind (), sd->get_index ());
1305 /* Dump this to PP in a form suitable for use as an id in .dot output. */
1308 exploded_node::dump_dot_id (pretty_printer *pp) const
1310 pp_printf (pp, "exploded_node_%i", m_index);
1313 /* Dump a multiline representation of this node to PP. */
1316 exploded_node::dump_to_pp (pretty_printer *pp,
1317 const extrinsic_state &ext_state) const
1319 pp_printf (pp, "EN: %i", m_index);
1323 m_ps.get_point ().print (pp, f);
1326 m_ps.get_state ().dump_to_pp (ext_state, false, true, pp);
1330 /* Dump a multiline representation of this node to FILE. */
1333 exploded_node::dump (FILE *fp,
1334 const extrinsic_state &ext_state) const
1337 pp_format_decoder (&pp) = default_tree_printer;
1338 pp_show_color (&pp) = pp_show_color (global_dc->printer);
1339 pp.buffer->stream = fp;
1340 dump_to_pp (&pp, ext_state);
1344 /* Dump a multiline representation of this node to stderr. */
1347 exploded_node::dump (const extrinsic_state &ext_state) const
1349 dump (stderr, ext_state);
1352 /* Return a new json::object of the form
1353 {"point" : object for program_point,
1354 "state" : object for program_state,
1357 "processed_stmts" : int}. */
1360 exploded_node::to_json (const extrinsic_state &ext_state) const
1362 json::object *enode_obj = new json::object ();
1364 enode_obj->set ("point", get_point ().to_json ());
1365 enode_obj->set ("state", get_state ().to_json (ext_state));
1366 enode_obj->set ("status", new json::string (status_to_str (m_status)));
1367 enode_obj->set ("idx", new json::integer_number (m_index));
1368 enode_obj->set ("processed_stmts",
1369 new json::integer_number (m_num_processed_stmts));
1376 /* Return true if FNDECL has a gimple body. */
1377 // TODO: is there a pre-canned way to do this?
1380 fndecl_has_gimple_body_p (tree fndecl)
1382 if (fndecl == NULL_TREE)
1385 cgraph_node *n = cgraph_node::get (fndecl);
1389 return n->has_gimple_body_p ();
1394 /* Modify STATE in place, applying the effects of the stmt at this node's
1397 exploded_node::on_stmt_flags
1398 exploded_node::on_stmt (exploded_graph &eg,
1399 const supernode *snode,
1401 program_state *state,
1402 uncertainty_t *uncertainty,
1403 path_context *path_ctxt)
1405 logger *logger = eg.get_logger ();
1409 logger->start_log_line ();
1410 pp_gimple_stmt_1 (logger->get_printer (), stmt, 0, (dump_flags_t)0);
1411 logger->end_log_line ();
1414 /* Update input_location in case of ICE: make it easier to track down which
1415 source construct we're failing to handle. */
1416 input_location = stmt->location;
1418 gcc_assert (state->m_region_model);
1420 /* Preserve the old state. It is used here for looking
1421 up old checker states, for determining state transitions, and
1422 also within impl_region_model_context and impl_sm_context for
1423 going from tree to svalue_id. */
1424 const program_state old_state (*state);
1426 impl_region_model_context ctxt (eg, this,
1427 &old_state, state, uncertainty,
1430 /* Handle call summaries here. */
1431 if (cgraph_edge *cgedge
1432 = supergraph_call_edge (snode->get_function (), stmt))
1433 if (eg.get_analysis_plan ().use_summary_p (cgedge))
1435 function *called_fn = get_ultimate_function_for_cgraph_edge (cgedge);
1436 per_function_data *called_fn_data
1437 = eg.get_per_function_data (called_fn);
1439 return replay_call_summaries (eg,
1441 as_a <const gcall *> (stmt),
1449 bool unknown_side_effects = false;
1450 bool terminate_path = false;
1452 on_stmt_pre (eg, stmt, state, &terminate_path,
1453 &unknown_side_effects, &ctxt);
1456 return on_stmt_flags::terminate_path ();
1460 FOR_EACH_VEC_ELT (old_state.m_checker_states, sm_idx, smap)
1462 const state_machine &sm = eg.get_ext_state ().get_sm (sm_idx);
1463 const sm_state_map *old_smap
1464 = old_state.m_checker_states[sm_idx];
1465 sm_state_map *new_smap = state->m_checker_states[sm_idx];
1466 impl_sm_context sm_ctxt (eg, sm_idx, sm, this, &old_state, state,
1467 old_smap, new_smap, path_ctxt, NULL,
1468 unknown_side_effects);
1470 /* Allow the state_machine to handle the stmt. */
1471 if (sm.on_stmt (&sm_ctxt, snode, stmt))
1472 unknown_side_effects = false;
1475 if (path_ctxt->terminate_path_p ())
1476 return on_stmt_flags::terminate_path ();
1478 on_stmt_post (stmt, state, unknown_side_effects, &ctxt);
1480 return on_stmt_flags ();
1483 /* Handle the pre-sm-state part of STMT, modifying STATE in-place.
1484 Write true to *OUT_TERMINATE_PATH if the path should be terminated.
1485 Write true to *OUT_UNKNOWN_SIDE_EFFECTS if the stmt has unknown
1489 exploded_node::on_stmt_pre (exploded_graph &eg,
1491 program_state *state,
1492 bool *out_terminate_path,
1493 bool *out_unknown_side_effects,
1494 region_model_context *ctxt)
1496 /* Handle special-case calls that require the full program_state. */
1497 if (const gcall *call = dyn_cast <const gcall *> (stmt))
1499 if (is_special_named_call_p (call, "__analyzer_dump", 0))
1501 /* Handle the builtin "__analyzer_dump" by dumping state
1503 state->dump (eg.get_ext_state (), true);
1506 else if (is_special_named_call_p (call, "__analyzer_dump_state", 2))
1508 state->impl_call_analyzer_dump_state (call, eg.get_ext_state (),
1512 else if (is_setjmp_call_p (call))
1514 state->m_region_model->on_setjmp (call, this, ctxt);
1517 else if (is_longjmp_call_p (call))
1519 on_longjmp (eg, call, state, ctxt);
1520 *out_terminate_path = true;
1525 /* Otherwise, defer to m_region_model. */
1526 state->m_region_model->on_stmt_pre (stmt,
1527 out_unknown_side_effects,
1531 /* Handle the post-sm-state part of STMT, modifying STATE in-place. */
1534 exploded_node::on_stmt_post (const gimple *stmt,
1535 program_state *state,
1536 bool unknown_side_effects,
1537 region_model_context *ctxt)
1539 if (const gcall *call = dyn_cast <const gcall *> (stmt))
1540 state->m_region_model->on_call_post (call, unknown_side_effects, ctxt);
1543 /* A concrete call_info subclass representing a replay of a call summary. */
1545 class call_summary_edge_info : public call_info
1548 call_summary_edge_info (const call_details &cd,
1549 function *called_fn,
1550 call_summary *summary,
1551 const extrinsic_state &ext_state)
1553 m_called_fn (called_fn),
1554 m_summary (summary),
1555 m_ext_state (ext_state)
1558 bool update_state (program_state *state,
1559 const exploded_edge *,
1560 region_model_context *ctxt) const final override
1562 /* Update STATE based on summary_end_state. */
1563 call_details cd (get_call_details (state->m_region_model, ctxt));
1564 call_summary_replay r (cd, m_called_fn, m_summary, m_ext_state);
1565 const program_state &summary_end_state = m_summary->get_state ();
1566 return state->replay_call_summary (r, summary_end_state);
1569 bool update_model (region_model *model,
1570 const exploded_edge *,
1571 region_model_context *ctxt) const final override
1573 /* Update STATE based on summary_end_state. */
1574 call_details cd (get_call_details (model, ctxt));
1575 call_summary_replay r (cd, m_called_fn, m_summary, m_ext_state);
1576 const program_state &summary_end_state = m_summary->get_state ();
1577 model->replay_call_summary (r, *summary_end_state.m_region_model);
1581 label_text get_desc (bool /*can_colorize*/) const final override
1583 return m_summary->get_desc ();
1587 function *m_called_fn;
1588 call_summary *m_summary;
1589 const extrinsic_state &m_ext_state;
1592 /* Use PATH_CTXT to bifurcate, which when handled will add custom edges
1593 for a replay of the various feasible summaries in CALLED_FN_DATA. */
1595 exploded_node::on_stmt_flags
1596 exploded_node::replay_call_summaries (exploded_graph &eg,
1597 const supernode *snode,
1598 const gcall *call_stmt,
1599 program_state *state,
1600 path_context *path_ctxt,
1601 function *called_fn,
1602 per_function_data *called_fn_data,
1603 region_model_context *ctxt)
1605 logger *logger = eg.get_logger ();
1608 gcc_assert (called_fn);
1609 gcc_assert (called_fn_data);
1611 /* Each summary will call bifurcate on the PATH_CTXT. */
1612 for (auto summary : called_fn_data->m_summaries)
1613 replay_call_summary (eg, snode, call_stmt, state,
1614 path_ctxt, called_fn, summary, ctxt);
1615 path_ctxt->terminate_path ();
1617 return on_stmt_flags ();
1620 /* Use PATH_CTXT to bifurcate, which when handled will add a
1621 custom edge for a replay of SUMMARY, if the summary's
1622 conditions are feasible based on the current state. */
1625 exploded_node::replay_call_summary (exploded_graph &eg,
1626 const supernode *snode,
1627 const gcall *call_stmt,
1628 program_state *old_state,
1629 path_context *path_ctxt,
1630 function *called_fn,
1631 call_summary *summary,
1632 region_model_context *ctxt)
1634 logger *logger = eg.get_logger ();
1637 gcc_assert (call_stmt);
1638 gcc_assert (old_state);
1639 gcc_assert (called_fn);
1640 gcc_assert (summary);
1643 logger->log ("using %s as summary for call to %qE from %qE",
1644 summary->get_desc ().get (),
1646 snode->get_function ()->decl);
1647 const extrinsic_state &ext_state = eg.get_ext_state ();
1648 const program_state &summary_end_state = summary->get_state ();
1651 pretty_printer *pp = logger->get_printer ();
1653 logger->start_log_line ();
1654 pp_string (pp, "callsite state: ");
1655 old_state->dump_to_pp (ext_state, true, false, pp);
1656 logger->end_log_line ();
1658 logger->start_log_line ();
1659 pp_string (pp, "summary end state: ");
1660 summary_end_state.dump_to_pp (ext_state, true, false, pp);
1661 logger->end_log_line ();
1664 program_state new_state (*old_state);
1666 call_details cd (call_stmt, new_state.m_region_model, ctxt);
1667 call_summary_replay r (cd, called_fn, summary, ext_state);
1670 path_ctxt->bifurcate (make_unique<call_summary_edge_info> (cd,
1677 /* Consider the effect of following superedge SUCC from this node.
1679 Return true if it's feasible to follow the edge, or false
1682 Examples: if it's the "true" branch within
1683 a CFG and we know the conditional is false, we know it's infeasible.
1684 If it's one of multiple interprocedual "return" edges, then only
1685 the edge back to the most recent callsite is feasible.
1687 Update NEXT_STATE accordingly (e.g. to record that a condition was
1688 true or false, or that the NULL-ness of a pointer has been checked,
1689 pushing/popping stack frames, etc).
1691 Update NEXT_POINT accordingly (updating the call string). */
1694 exploded_node::on_edge (exploded_graph &eg,
1695 const superedge *succ,
1696 program_point *next_point,
1697 program_state *next_state,
1698 uncertainty_t *uncertainty)
1700 LOG_FUNC (eg.get_logger ());
1702 if (!next_point->on_edge (eg, succ))
1705 if (!next_state->on_edge (eg, this, succ, uncertainty))
1711 /* Verify that the stack at LONGJMP_POINT is still valid, given a call
1712 to "setjmp" at SETJMP_POINT - the stack frame that "setjmp" was
1713 called in must still be valid.
1715 Caveat: this merely checks the call_strings in the points; it doesn't
1716 detect the case where a frame returns and is then called again. */
1719 valid_longjmp_stack_p (const program_point &longjmp_point,
1720 const program_point &setjmp_point)
1722 const call_string &cs_at_longjmp = longjmp_point.get_call_string ();
1723 const call_string &cs_at_setjmp = setjmp_point.get_call_string ();
1725 if (cs_at_longjmp.length () < cs_at_setjmp.length ())
1728 /* Check that the call strings match, up to the depth of the
1730 for (unsigned depth = 0; depth < cs_at_setjmp.length (); depth++)
1731 if (cs_at_longjmp[depth] != cs_at_setjmp[depth])
1737 /* A pending_diagnostic subclass for complaining about bad longjmps,
1738 where the enclosing function of the "setjmp" has returned (and thus
1739 the stack frame no longer exists). */
1741 class stale_jmp_buf : public pending_diagnostic_subclass<stale_jmp_buf>
1744 stale_jmp_buf (const gcall *setjmp_call, const gcall *longjmp_call,
1745 const program_point &setjmp_point)
1746 : m_setjmp_call (setjmp_call), m_longjmp_call (longjmp_call),
1747 m_setjmp_point (setjmp_point), m_stack_pop_event (NULL)
1750 int get_controlling_option () const final override
1752 return OPT_Wanalyzer_stale_setjmp_buffer;
1755 bool emit (rich_location *richloc) final override
1758 (richloc, get_controlling_option (),
1759 "%qs called after enclosing function of %qs has returned",
1760 get_user_facing_name (m_longjmp_call),
1761 get_user_facing_name (m_setjmp_call));
1764 const char *get_kind () const final override
1765 { return "stale_jmp_buf"; }
1767 bool operator== (const stale_jmp_buf &other) const
1769 return (m_setjmp_call == other.m_setjmp_call
1770 && m_longjmp_call == other.m_longjmp_call);
1774 maybe_add_custom_events_for_superedge (const exploded_edge &eedge,
1775 checker_path *emission_path)
1778 /* Detect exactly when the stack first becomes invalid,
1779 and issue an event then. */
1780 if (m_stack_pop_event)
1782 const exploded_node *src_node = eedge.m_src;
1783 const program_point &src_point = src_node->get_point ();
1784 const exploded_node *dst_node = eedge.m_dest;
1785 const program_point &dst_point = dst_node->get_point ();
1786 if (valid_longjmp_stack_p (src_point, m_setjmp_point)
1787 && !valid_longjmp_stack_p (dst_point, m_setjmp_point))
1789 /* Compare with diagnostic_manager::add_events_for_superedge. */
1790 const int src_stack_depth = src_point.get_stack_depth ();
1791 m_stack_pop_event = new precanned_custom_event
1792 (event_loc_info (src_point.get_location (),
1793 src_point.get_fndecl (),
1795 "stack frame is popped here, invalidating saved environment");
1796 emission_path->add_event
1797 (std::unique_ptr<custom_event> (m_stack_pop_event));
1803 label_text describe_final_event (const evdesc::final_event &ev) final override
1805 if (m_stack_pop_event)
1806 return ev.formatted_print
1807 ("%qs called after enclosing function of %qs returned at %@",
1808 get_user_facing_name (m_longjmp_call),
1809 get_user_facing_name (m_setjmp_call),
1810 m_stack_pop_event->get_id_ptr ());
1812 return ev.formatted_print
1813 ("%qs called after enclosing function of %qs has returned",
1814 get_user_facing_name (m_longjmp_call),
1815 get_user_facing_name (m_setjmp_call));;
1820 const gcall *m_setjmp_call;
1821 const gcall *m_longjmp_call;
1822 program_point m_setjmp_point;
1823 custom_event *m_stack_pop_event;
1826 /* Handle LONGJMP_CALL, a call to longjmp or siglongjmp.
1828 Attempt to locate where setjmp/sigsetjmp was called on the jmp_buf and build
1829 an exploded_node and exploded_edge to it representing a rewind to that frame,
1830 handling the various kinds of failure that can occur. */
1833 exploded_node::on_longjmp (exploded_graph &eg,
1834 const gcall *longjmp_call,
1835 program_state *new_state,
1836 region_model_context *ctxt)
1838 tree buf_ptr = gimple_call_arg (longjmp_call, 0);
1839 gcc_assert (POINTER_TYPE_P (TREE_TYPE (buf_ptr)));
1841 region_model *new_region_model = new_state->m_region_model;
1842 const svalue *buf_ptr_sval = new_region_model->get_rvalue (buf_ptr, ctxt);
1843 const region *buf = new_region_model->deref_rvalue (buf_ptr_sval, buf_ptr,
1846 const svalue *buf_content_sval
1847 = new_region_model->get_store_value (buf, ctxt);
1848 const setjmp_svalue *setjmp_sval
1849 = buf_content_sval->dyn_cast_setjmp_svalue ();
1853 const setjmp_record tmp_setjmp_record = setjmp_sval->get_setjmp_record ();
1855 /* Build a custom enode and eedge for rewinding from the longjmp/siglongjmp
1856 call back to the setjmp/sigsetjmp. */
1857 rewind_info_t rewind_info (tmp_setjmp_record, longjmp_call);
1859 const gcall *setjmp_call = rewind_info.get_setjmp_call ();
1860 const program_point &setjmp_point = rewind_info.get_setjmp_point ();
1862 const program_point &longjmp_point = get_point ();
1864 /* Verify that the setjmp's call_stack hasn't been popped. */
1865 if (!valid_longjmp_stack_p (longjmp_point, setjmp_point))
1867 ctxt->warn (make_unique<stale_jmp_buf> (setjmp_call,
1873 gcc_assert (longjmp_point.get_stack_depth ()
1874 >= setjmp_point.get_stack_depth ());
1876 /* Update the state for use by the destination node. */
1878 /* Stash the current number of diagnostics so that we can update
1879 any that this adds to show where the longjmp is rewinding to. */
1881 diagnostic_manager *dm = &eg.get_diagnostic_manager ();
1882 unsigned prev_num_diagnostics = dm->get_num_diagnostics ();
1884 new_region_model->on_longjmp (longjmp_call, setjmp_call,
1885 setjmp_point.get_stack_depth (), ctxt);
1887 /* Detect leaks in the new state relative to the old state. */
1888 program_state::detect_leaks (get_state (), *new_state, NULL,
1889 eg.get_ext_state (), ctxt);
1891 program_point next_point
1892 = program_point::after_supernode (setjmp_point.get_supernode (),
1893 setjmp_point.get_call_string ());
1896 = eg.get_or_create_node (next_point, *new_state, this);
1898 /* Create custom exploded_edge for a longjmp. */
1901 exploded_edge *eedge
1902 = eg.add_edge (const_cast<exploded_node *> (this), next, NULL,
1903 make_unique<rewind_info_t> (tmp_setjmp_record, longjmp_call));
1905 /* For any diagnostics that were queued here (such as leaks) we want
1906 the checker_path to show the rewinding events after the "final event"
1907 so that the user sees where the longjmp is rewinding to (otherwise the
1908 path is meaningless).
1910 For example, we want to emit something like:
1912 | NN | longjmp (env, 1);
1913 | | ~~~~~~~~~~~~~~~~
1915 | | (10) 'ptr' leaks here; was allocated at (7)
1916 | | (11) rewinding from 'longjmp' in 'inner'...
1922 | NN | i = setjmp(env);
1925 | | (12) ...to 'setjmp' in 'outer' (saved at (2))
1927 where the "final" event above is event (10), but we want to append
1928 events (11) and (12) afterwards.
1930 Do this by setting m_trailing_eedge on any diagnostics that were
1932 unsigned num_diagnostics = dm->get_num_diagnostics ();
1933 for (unsigned i = prev_num_diagnostics; i < num_diagnostics; i++)
1935 saved_diagnostic *sd = dm->get_saved_diagnostic (i);
1936 sd->m_trailing_eedge = eedge;
1941 /* Subroutine of exploded_graph::process_node for finding the successors
1942 of the supernode for a function exit basic block.
1944 Ensure that pop_frame is called, potentially queuing diagnostics about
1948 exploded_node::detect_leaks (exploded_graph &eg)
1950 LOG_FUNC_1 (eg.get_logger (), "EN: %i", m_index);
1952 gcc_assert (get_point ().get_supernode ()->return_p ());
1954 /* If we're not a "top-level" function, do nothing; pop_frame
1955 will be called when handling the return superedge. */
1956 if (get_point ().get_stack_depth () > 1)
1959 /* We have a "top-level" function. */
1960 gcc_assert (get_point ().get_stack_depth () == 1);
1962 const program_state &old_state = get_state ();
1964 /* Work with a temporary copy of the state: pop the frame, and see
1965 what leaks (via purge_unused_svalues). */
1966 program_state new_state (old_state);
1968 gcc_assert (new_state.m_region_model);
1970 uncertainty_t uncertainty;
1971 impl_region_model_context ctxt (eg, this,
1972 &old_state, &new_state, &uncertainty, NULL,
1974 const svalue *result = NULL;
1975 new_state.m_region_model->pop_frame (NULL, &result, &ctxt);
1976 program_state::detect_leaks (old_state, new_state, result,
1977 eg.get_ext_state (), &ctxt);
1980 /* Dump the successors and predecessors of this enode to OUTF. */
1983 exploded_node::dump_succs_and_preds (FILE *outf) const
1988 auto_vec<exploded_node *> preds (m_preds.length ());
1989 FOR_EACH_VEC_ELT (m_preds, i, e)
1990 preds.quick_push (e->m_src);
1992 print_enode_indices (&pp, preds);
1993 fprintf (outf, "preds: %s\n",
1994 pp_formatted_text (&pp));
1997 auto_vec<exploded_node *> succs (m_succs.length ());
1998 FOR_EACH_VEC_ELT (m_succs, i, e)
1999 succs.quick_push (e->m_dest);
2001 print_enode_indices (&pp, succs);
2002 fprintf (outf, "succs: %s\n",
2003 pp_formatted_text (&pp));
2007 /* class dynamic_call_info_t : public custom_edge_info. */
2009 /* Implementation of custom_edge_info::update_model vfunc
2010 for dynamic_call_info_t.
2012 Update state for a dynamically discovered call (or return), by pushing
2013 or popping the a frame for the appropriate function. */
2016 dynamic_call_info_t::update_model (region_model *model,
2017 const exploded_edge *eedge,
2018 region_model_context *ctxt) const
2021 if (m_is_returning_call)
2022 model->update_for_return_gcall (m_dynamic_call, ctxt);
2025 function *callee = eedge->m_dest->get_function ();
2026 model->update_for_gcall (m_dynamic_call, ctxt, callee);
2031 /* Implementation of custom_edge_info::add_events_to_path vfunc
2032 for dynamic_call_info_t. */
2035 dynamic_call_info_t::add_events_to_path (checker_path *emission_path,
2036 const exploded_edge &eedge) const
2038 const exploded_node *src_node = eedge.m_src;
2039 const program_point &src_point = src_node->get_point ();
2040 const int src_stack_depth = src_point.get_stack_depth ();
2041 const exploded_node *dest_node = eedge.m_dest;
2042 const program_point &dest_point = dest_node->get_point ();
2043 const int dest_stack_depth = dest_point.get_stack_depth ();
2045 if (m_is_returning_call)
2046 emission_path->add_event
2047 (make_unique<return_event> (eedge,
2048 event_loc_info (m_dynamic_call
2049 ? m_dynamic_call->location
2051 dest_point.get_fndecl (),
2052 dest_stack_depth)));
2054 emission_path->add_event
2055 (make_unique<call_event> (eedge,
2056 event_loc_info (m_dynamic_call
2057 ? m_dynamic_call->location
2059 src_point.get_fndecl (),
2063 /* class rewind_info_t : public custom_edge_info. */
2065 /* Implementation of custom_edge_info::update_model vfunc
2068 Update state for the special-case of a rewind of a longjmp
2069 to a setjmp (which doesn't have a superedge, but does affect
2073 rewind_info_t::update_model (region_model *model,
2074 const exploded_edge *eedge,
2075 region_model_context *) const
2078 const program_point &longjmp_point = eedge->m_src->get_point ();
2079 const program_point &setjmp_point = eedge->m_dest->get_point ();
2081 gcc_assert (longjmp_point.get_stack_depth ()
2082 >= setjmp_point.get_stack_depth ());
2084 model->on_longjmp (get_longjmp_call (),
2086 setjmp_point.get_stack_depth (), NULL);
2090 /* Implementation of custom_edge_info::add_events_to_path vfunc
2091 for rewind_info_t. */
2094 rewind_info_t::add_events_to_path (checker_path *emission_path,
2095 const exploded_edge &eedge) const
2097 const exploded_node *src_node = eedge.m_src;
2098 const program_point &src_point = src_node->get_point ();
2099 const int src_stack_depth = src_point.get_stack_depth ();
2100 const exploded_node *dst_node = eedge.m_dest;
2101 const program_point &dst_point = dst_node->get_point ();
2102 const int dst_stack_depth = dst_point.get_stack_depth ();
2104 emission_path->add_event
2105 (make_unique<rewind_from_longjmp_event>
2107 event_loc_info (get_longjmp_call ()->location,
2108 src_point.get_fndecl (),
2111 emission_path->add_event
2112 (make_unique<rewind_to_setjmp_event>
2114 event_loc_info (get_setjmp_call ()->location,
2115 dst_point.get_fndecl (),
2120 /* class exploded_edge : public dedge<eg_traits>. */
2122 /* exploded_edge's ctor. */
2124 exploded_edge::exploded_edge (exploded_node *src, exploded_node *dest,
2125 const superedge *sedge,
2126 std::unique_ptr<custom_edge_info> custom_info)
2127 : dedge<eg_traits> (src, dest), m_sedge (sedge),
2128 m_custom_info (std::move (custom_info))
2132 /* Implementation of dedge::dump_dot vfunc for exploded_edge.
2133 Use the label of the underlying superedge, if any. */
2136 exploded_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const
2138 pretty_printer *pp = gv->get_pp ();
2140 m_src->dump_dot_id (pp);
2141 pp_string (pp, " -> ");
2142 m_dest->dump_dot_id (pp);
2143 dump_dot_label (pp);
2146 /* Second half of exploded_edge::dump_dot. This is split out
2147 for use by trimmed_graph::dump_dot and base_feasible_edge::dump_dot. */
2150 exploded_edge::dump_dot_label (pretty_printer *pp) const
2152 const char *style = "\"solid,bold\"";
2153 const char *color = "black";
2155 const char *constraint = "true";
2158 switch (m_sedge->m_kind)
2162 case SUPEREDGE_CFG_EDGE:
2164 case SUPEREDGE_CALL:
2166 //constraint = "false";
2168 case SUPEREDGE_RETURN:
2170 //constraint = "false";
2172 case SUPEREDGE_INTRAPROCEDURAL_CALL:
2173 style = "\"dotted\"";
2179 style = "\"dotted\"";
2183 (" [style=%s, color=%s, weight=%d, constraint=%s,"
2185 style, color, weight, constraint);
2188 m_sedge->dump_label_to_pp (pp, false);
2189 else if (m_custom_info)
2190 m_custom_info->print (pp);
2192 //pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
2194 pp_printf (pp, "\"];\n");
2197 /* Return a new json::object of the form
2198 {"src_idx": int, the index of the source exploded edge,
2199 "dst_idx": int, the index of the destination exploded edge,
2200 "sedge": (optional) object for the superedge, if any,
2201 "custom": (optional) str, a description, if this is a custom edge}. */
2204 exploded_edge::to_json () const
2206 json::object *eedge_obj = new json::object ();
2207 eedge_obj->set ("src_idx", new json::integer_number (m_src->m_index));
2208 eedge_obj->set ("dst_idx", new json::integer_number (m_dest->m_index));
2210 eedge_obj->set ("sedge", m_sedge->to_json ());
2214 pp_format_decoder (&pp) = default_tree_printer;
2215 m_custom_info->print (&pp);
2216 eedge_obj->set ("custom", new json::string (pp_formatted_text (&pp)));
2225 stats::stats (int num_supernodes)
2226 : m_node_reuse_count (0),
2227 m_node_reuse_after_merge_count (0),
2228 m_num_supernodes (num_supernodes)
2230 for (int i = 0; i < NUM_POINT_KINDS; i++)
2234 /* Log these stats in multiline form to LOGGER. */
2237 stats::log (logger *logger) const
2239 gcc_assert (logger);
2240 for (int i = 0; i < NUM_POINT_KINDS; i++)
2241 if (m_num_nodes[i] > 0)
2242 logger->log ("m_num_nodes[%s]: %i",
2243 point_kind_to_string (static_cast <enum point_kind> (i)),
2245 logger->log ("m_node_reuse_count: %i", m_node_reuse_count);
2246 logger->log ("m_node_reuse_after_merge_count: %i",
2247 m_node_reuse_after_merge_count);
2250 /* Dump these stats in multiline form to OUT. */
2253 stats::dump (FILE *out) const
2255 for (int i = 0; i < NUM_POINT_KINDS; i++)
2256 if (m_num_nodes[i] > 0)
2257 fprintf (out, "m_num_nodes[%s]: %i\n",
2258 point_kind_to_string (static_cast <enum point_kind> (i)),
2260 fprintf (out, "m_node_reuse_count: %i\n", m_node_reuse_count);
2261 fprintf (out, "m_node_reuse_after_merge_count: %i\n",
2262 m_node_reuse_after_merge_count);
2264 if (m_num_supernodes > 0)
2265 fprintf (out, "PK_AFTER_SUPERNODE nodes per supernode: %.2f\n",
2266 (float)m_num_nodes[PK_AFTER_SUPERNODE] / (float)m_num_supernodes);
2269 /* Return the total number of enodes recorded within this object. */
2272 stats::get_total_enodes () const
2275 for (int i = 0; i < NUM_POINT_KINDS; i++)
2276 result += m_num_nodes[i];
2280 /* struct per_function_data. */
2282 per_function_data::~per_function_data ()
2284 for (auto iter : m_summaries)
2289 per_function_data::add_call_summary (exploded_node *node)
2291 m_summaries.safe_push (new call_summary (this, node));
2294 /* strongly_connected_components's ctor. Tarjan's SCC algorithm. */
2296 strongly_connected_components::
2297 strongly_connected_components (const supergraph &sg, logger *logger)
2298 : m_sg (sg), m_per_node (m_sg.num_nodes ())
2301 auto_timevar tv (TV_ANALYZER_SCC);
2303 for (int i = 0; i < m_sg.num_nodes (); i++)
2304 m_per_node.quick_push (per_node_data ());
2306 for (int i = 0; i < m_sg.num_nodes (); i++)
2307 if (m_per_node[i].m_index == -1)
2314 /* Dump this object to stderr. */
2317 strongly_connected_components::dump () const
2319 for (int i = 0; i < m_sg.num_nodes (); i++)
2321 const per_node_data &v = m_per_node[i];
2322 fprintf (stderr, "SN %i: index: %i lowlink: %i on_stack: %i\n",
2323 i, v.m_index, v.m_lowlink, v.m_on_stack);
2327 /* Return a new json::array of per-snode SCC ids. */
2330 strongly_connected_components::to_json () const
2332 json::array *scc_arr = new json::array ();
2333 for (int i = 0; i < m_sg.num_nodes (); i++)
2334 scc_arr->append (new json::integer_number (get_scc_id (i)));
2338 /* Subroutine of strongly_connected_components's ctor, part of Tarjan's
2342 strongly_connected_components::strong_connect (unsigned index)
2344 supernode *v_snode = m_sg.get_node_by_index (index);
2346 /* Set the depth index for v to the smallest unused index. */
2347 per_node_data *v = &m_per_node[index];
2349 v->m_lowlink = index;
2350 m_stack.safe_push (index);
2351 v->m_on_stack = true;
2354 /* Consider successors of v. */
2357 FOR_EACH_VEC_ELT (v_snode->m_succs, i, sedge)
2359 if (sedge->get_kind () != SUPEREDGE_CFG_EDGE
2360 && sedge->get_kind () != SUPEREDGE_INTRAPROCEDURAL_CALL)
2362 supernode *w_snode = sedge->m_dest;
2363 per_node_data *w = &m_per_node[w_snode->m_index];
2364 if (w->m_index == -1)
2366 /* Successor w has not yet been visited; recurse on it. */
2367 strong_connect (w_snode->m_index);
2368 v->m_lowlink = MIN (v->m_lowlink, w->m_lowlink);
2370 else if (w->m_on_stack)
2372 /* Successor w is in stack S and hence in the current SCC
2373 If w is not on stack, then (v, w) is a cross-edge in the DFS
2374 tree and must be ignored. */
2375 v->m_lowlink = MIN (v->m_lowlink, w->m_index);
2379 /* If v is a root node, pop the stack and generate an SCC. */
2381 if (v->m_lowlink == v->m_index)
2385 int idx = m_stack.pop ();
2386 w = &m_per_node[idx];
2387 w->m_on_stack = false;
2392 /* worklist's ctor. */
2394 worklist::worklist (const exploded_graph &eg, const analysis_plan &plan)
2395 : m_scc (eg.get_supergraph (), eg.get_logger ()),
2397 m_queue (key_t (*this, NULL))
2401 /* Return the number of nodes in the worklist. */
2404 worklist::length () const
2406 return m_queue.nodes ();
2409 /* Return the next node in the worklist, removing it. */
2412 worklist::take_next ()
2414 return m_queue.extract_min ();
2417 /* Return the next node in the worklist without removing it. */
2420 worklist::peek_next ()
2422 return m_queue.min ();
2425 /* Add ENODE to the worklist. */
2428 worklist::add_node (exploded_node *enode)
2430 gcc_assert (enode->get_status () == exploded_node::STATUS_WORKLIST);
2431 m_queue.insert (key_t (*this, enode), enode);
2434 /* Comparator for implementing worklist::key_t comparison operators.
2435 Return negative if KA is before KB
2436 Return positive if KA is after KB
2437 Return 0 if they are equal.
2439 The ordering of the worklist is critical for performance and for
2440 avoiding node explosions. Ideally we want all enodes at a CFG join-point
2441 with the same callstring to be sorted next to each other in the worklist
2442 so that a run of consecutive enodes can be merged and processed "in bulk"
2443 rather than individually or pairwise, minimizing the number of new enodes
2447 worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb)
2449 const program_point &point_a = ka.m_enode->get_point ();
2450 const program_point &point_b = kb.m_enode->get_point ();
2451 const call_string &call_string_a = point_a.get_call_string ();
2452 const call_string &call_string_b = point_b.get_call_string ();
2454 /* Order empty-callstring points with different functions based on the
2455 analysis_plan, so that we generate summaries before they are used. */
2456 if (flag_analyzer_call_summaries
2457 && call_string_a.empty_p ()
2458 && call_string_b.empty_p ()
2459 && point_a.get_function () != NULL
2460 && point_b.get_function () != NULL
2461 && point_a.get_function () != point_b.get_function ())
2463 if (int cmp = ka.m_worklist.m_plan.cmp_function (point_a.get_function (),
2464 point_b.get_function ()))
2468 /* Sort by callstring, so that nodes with deeper call strings are processed
2469 before those with shallower call strings.
2478 then we want the path inside the function call to be fully explored up
2479 to the return to the join BB before we explore on the "no fn call" path,
2480 so that both enodes at the join BB reach the front of the worklist at
2481 the same time and thus have a chance of being merged. */
2482 int cs_cmp = call_string::cmp (call_string_a, call_string_b);
2487 int scc_id_a = ka.get_scc_id (ka.m_enode);
2488 int scc_id_b = kb.get_scc_id (kb.m_enode);
2489 if (scc_id_a != scc_id_b)
2490 return scc_id_a - scc_id_b;
2492 /* If in same SCC, order by supernode index (an arbitrary but stable
2494 const supernode *snode_a = ka.m_enode->get_supernode ();
2495 const supernode *snode_b = kb.m_enode->get_supernode ();
2496 if (snode_a == NULL)
2498 if (snode_b != NULL)
2502 /* Both are NULL. */
2505 if (snode_b == NULL)
2508 /* Neither are NULL. */
2509 gcc_assert (snode_a && snode_b);
2510 if (snode_a->m_index != snode_b->m_index)
2511 return snode_a->m_index - snode_b->m_index;
2513 gcc_assert (snode_a == snode_b);
2515 /* Order within supernode via program point. */
2516 int within_snode_cmp
2517 = function_point::cmp_within_supernode (point_a.get_function_point (),
2518 point_b.get_function_point ());
2519 if (within_snode_cmp)
2520 return within_snode_cmp;
2522 /* Otherwise, we ought to have the same program_point. */
2523 gcc_assert (point_a == point_b);
2525 const program_state &state_a = ka.m_enode->get_state ();
2526 const program_state &state_b = kb.m_enode->get_state ();
2528 /* Sort by sm-state, so that identical sm-states are grouped
2529 together in the worklist. */
2530 for (unsigned sm_idx = 0; sm_idx < state_a.m_checker_states.length ();
2533 sm_state_map *smap_a = state_a.m_checker_states[sm_idx];
2534 sm_state_map *smap_b = state_b.m_checker_states[sm_idx];
2536 if (int smap_cmp = sm_state_map::cmp (*smap_a, *smap_b))
2540 /* Otherwise, we have two enodes at the same program point but with
2541 different states. We don't have a good total ordering on states,
2542 so order them by enode index, so that we have at least have a
2544 return ka.m_enode->m_index - kb.m_enode->m_index;
2547 /* Return a new json::object of the form
2548 {"scc" : [per-snode-IDs]}, */
2551 worklist::to_json () const
2553 json::object *worklist_obj = new json::object ();
2555 worklist_obj->set ("scc", m_scc.to_json ());
2557 /* The following field isn't yet being JSONified:
2560 return worklist_obj;
2563 /* exploded_graph's ctor. */
2565 exploded_graph::exploded_graph (const supergraph &sg, logger *logger,
2566 const extrinsic_state &ext_state,
2567 const state_purge_map *purge_map,
2568 const analysis_plan &plan,
2570 : m_sg (sg), m_logger (logger),
2571 m_worklist (*this, plan),
2572 m_ext_state (ext_state),
2573 m_purge_map (purge_map),
2575 m_diagnostic_manager (logger, ext_state.get_engine (), verbosity),
2576 m_global_stats (m_sg.num_nodes ()),
2577 m_functionless_stats (m_sg.num_nodes ()),
2578 m_PK_AFTER_SUPERNODE_per_snode (m_sg.num_nodes ())
2580 m_origin = get_or_create_node
2581 (program_point::origin (*ext_state.get_model_manager ()),
2582 program_state (ext_state), NULL);
2583 for (int i = 0; i < m_sg.num_nodes (); i++)
2584 m_PK_AFTER_SUPERNODE_per_snode.quick_push (i);
2587 /* exploded_graph's dtor. */
2589 exploded_graph::~exploded_graph ()
2591 for (auto iter : m_per_point_data)
2593 for (auto iter : m_per_function_data)
2595 for (auto iter : m_per_function_stats)
2597 for (auto iter : m_per_call_string_data)
2601 /* Subroutine for use when implementing __attribute__((tainted_args))
2602 on functions and on function pointer fields in structs.
2604 Called on STATE representing a call to FNDECL.
2605 Mark all params of FNDECL in STATE as "tainted". Mark the value of all
2606 regions pointed to by params of FNDECL as "tainted".
2608 Return true if successful; return false if the "taint" state machine
2612 mark_params_as_tainted (program_state *state, tree fndecl,
2613 const extrinsic_state &ext_state)
2615 unsigned taint_sm_idx;
2616 if (!ext_state.get_sm_idx_by_name ("taint", &taint_sm_idx))
2618 sm_state_map *smap = state->m_checker_states[taint_sm_idx];
2620 const state_machine &sm = ext_state.get_sm (taint_sm_idx);
2621 state_machine::state_t tainted = sm.get_state_by_name ("tainted");
2623 region_model_manager *mgr = ext_state.get_model_manager ();
2625 function *fun = DECL_STRUCT_FUNCTION (fndecl);
2628 for (tree iter_parm = DECL_ARGUMENTS (fndecl); iter_parm;
2629 iter_parm = DECL_CHAIN (iter_parm))
2631 tree param = iter_parm;
2632 if (tree parm_default_ssa = ssa_default_def (fun, iter_parm))
2633 param = parm_default_ssa;
2634 const region *param_reg = state->m_region_model->get_lvalue (param, NULL);
2635 const svalue *init_sval = mgr->get_or_create_initial_value (param_reg);
2636 smap->set_state (state->m_region_model, init_sval,
2637 tainted, NULL /*origin_new_sval*/, ext_state);
2638 if (POINTER_TYPE_P (TREE_TYPE (param)))
2640 const region *pointee_reg = mgr->get_symbolic_region (init_sval);
2641 /* Mark "*param" as tainted. */
2642 const svalue *init_pointee_sval
2643 = mgr->get_or_create_initial_value (pointee_reg);
2644 smap->set_state (state->m_region_model, init_pointee_sval,
2645 tainted, NULL /*origin_new_sval*/, ext_state);
2652 /* Custom event for use by tainted_args_function_info when a function
2653 has been marked with __attribute__((tainted_args)). */
2655 class tainted_args_function_custom_event : public custom_event
2658 tainted_args_function_custom_event (const event_loc_info &loc_info)
2659 : custom_event (loc_info),
2660 m_fndecl (loc_info.m_fndecl)
2664 label_text get_desc (bool can_colorize) const final override
2666 return make_label_text
2668 "function %qE marked with %<__attribute__((tainted_args))%>",
2676 /* Custom exploded_edge info for top-level calls to a function
2677 marked with __attribute__((tainted_args)). */
2679 class tainted_args_function_info : public custom_edge_info
2682 tainted_args_function_info (tree fndecl)
2686 void print (pretty_printer *pp) const final override
2688 pp_string (pp, "call to tainted_args function");
2691 bool update_model (region_model *,
2692 const exploded_edge *,
2693 region_model_context *) const final override
2699 void add_events_to_path (checker_path *emission_path,
2700 const exploded_edge &) const final override
2702 emission_path->add_event
2703 (make_unique<tainted_args_function_custom_event>
2704 (event_loc_info (DECL_SOURCE_LOCATION (m_fndecl), m_fndecl, 0)));
2711 /* Ensure that there is an exploded_node representing an external call to
2712 FUN, adding it to the worklist if creating it.
2714 Add an edge from the origin exploded_node to the function entrypoint
2717 Return the exploded_node for the entrypoint to the function. */
2720 exploded_graph::add_function_entry (function *fun)
2722 gcc_assert (gimple_has_body_p (fun->decl));
2724 /* Be idempotent. */
2725 if (m_functions_with_enodes.contains (fun))
2727 logger * const logger = get_logger ();
2729 logger->log ("entrypoint for %qE already exists", fun->decl);
2734 = program_point::from_function_entry (*m_ext_state.get_model_manager (),
2736 program_state state (m_ext_state);
2737 state.push_frame (m_ext_state, fun);
2739 std::unique_ptr<custom_edge_info> edge_info = NULL;
2741 if (lookup_attribute ("tainted_args", DECL_ATTRIBUTES (fun->decl)))
2743 if (mark_params_as_tainted (&state, fun->decl, m_ext_state))
2744 edge_info = make_unique<tainted_args_function_info> (fun->decl);
2750 exploded_node *enode = get_or_create_node (point, state, NULL);
2754 add_edge (m_origin, enode, NULL, std::move (edge_info));
2756 m_functions_with_enodes.add (fun);
2761 /* Get or create an exploded_node for (POINT, STATE).
2762 If a new node is created, it is added to the worklist.
2764 Use ENODE_FOR_DIAG, a pre-existing enode, for any diagnostics
2765 that need to be emitted (e.g. when purging state *before* we have
2769 exploded_graph::get_or_create_node (const program_point &point,
2770 const program_state &state,
2771 exploded_node *enode_for_diag)
2773 logger * const logger = get_logger ();
2778 pretty_printer *pp = logger->get_printer ();
2779 logger->start_log_line ();
2780 pp_string (pp, "point: ");
2781 point.print (pp, f);
2782 logger->end_log_line ();
2783 logger->start_log_line ();
2784 pp_string (pp, "state: ");
2785 state.dump_to_pp (m_ext_state, true, false, pp);
2786 logger->end_log_line ();
2789 /* Stop exploring paths for which we don't know how to effectively
2794 logger->log ("invalid state; not creating node");
2798 auto_cfun sentinel (point.get_function ());
2800 state.validate (get_ext_state ());
2802 //state.dump (get_ext_state ());
2804 /* Prune state to try to improve the chances of a cache hit,
2805 avoiding generating redundant nodes. */
2806 uncertainty_t uncertainty;
2807 program_state pruned_state
2808 = state.prune_for_point (*this, point, enode_for_diag, &uncertainty);
2810 pruned_state.validate (get_ext_state ());
2812 //pruned_state.dump (get_ext_state ());
2816 pretty_printer *pp = logger->get_printer ();
2817 logger->start_log_line ();
2818 pp_string (pp, "pruned_state: ");
2819 pruned_state.dump_to_pp (m_ext_state, true, false, pp);
2820 logger->end_log_line ();
2821 pruned_state.m_region_model->dump_to_pp (logger->get_printer (), true,
2825 stats *per_fn_stats = get_or_create_function_stats (point.get_function ());
2828 = &get_or_create_per_call_string_data (point.get_call_string ())->m_stats;
2830 point_and_state ps (point, pruned_state);
2831 ps.validate (m_ext_state);
2832 if (exploded_node **slot = m_point_and_state_to_node.get (&ps))
2834 /* An exploded_node for PS already exists. */
2836 logger->log ("reused EN: %i", (*slot)->m_index);
2837 m_global_stats.m_node_reuse_count++;
2838 per_fn_stats->m_node_reuse_count++;
2839 per_cs_stats->m_node_reuse_count++;
2843 per_program_point_data *per_point_data
2844 = get_or_create_per_program_point_data (point);
2846 /* Consider merging state with another enode at this program_point. */
2847 if (flag_analyzer_state_merge)
2849 exploded_node *existing_enode;
2851 FOR_EACH_VEC_ELT (per_point_data->m_enodes, i, existing_enode)
2854 logger->log ("considering merging with existing EN: %i for point",
2855 existing_enode->m_index);
2856 gcc_assert (existing_enode->get_point () == point);
2857 const program_state &existing_state = existing_enode->get_state ();
2859 /* This merges successfully within the loop. */
2861 program_state merged_state (m_ext_state);
2862 if (pruned_state.can_merge_with_p (existing_state, m_ext_state, point,
2865 merged_state.validate (m_ext_state);
2867 logger->log ("merging new state with that of EN: %i",
2868 existing_enode->m_index);
2870 /* Try again for a cache hit.
2871 Whether we get one or not, merged_state's value_ids have no
2872 relationship to those of the input state, and thus to those
2873 of CHANGE, so we must purge any svalue_ids from *CHANGE. */
2874 ps.set_state (merged_state);
2876 if (exploded_node **slot = m_point_and_state_to_node.get (&ps))
2878 /* An exploded_node for PS already exists. */
2880 logger->log ("reused EN: %i", (*slot)->m_index);
2881 m_global_stats.m_node_reuse_after_merge_count++;
2882 per_fn_stats->m_node_reuse_after_merge_count++;
2883 per_cs_stats->m_node_reuse_after_merge_count++;
2889 logger->log ("not merging new state with that of EN: %i",
2890 existing_enode->m_index);
2894 /* Impose a limit on the number of enodes per program point, and
2895 simply stop if we exceed it. */
2896 if ((int)per_point_data->m_enodes.length ()
2897 >= param_analyzer_max_enodes_per_program_point)
2900 point.print (&pp, format (false));
2901 print_enode_indices (&pp, per_point_data->m_enodes);
2903 logger->log ("not creating enode; too many at program point: %s",
2904 pp_formatted_text (&pp));
2905 warning_at (point.get_location (), OPT_Wanalyzer_too_complex,
2906 "terminating analysis for this program point: %s",
2907 pp_formatted_text (&pp));
2908 per_point_data->m_excess_enodes++;
2912 ps.validate (m_ext_state);
2914 /* An exploded_node for "ps" doesn't already exist; create one. */
2915 exploded_node *node = new exploded_node (ps, m_nodes.length ());
2917 m_point_and_state_to_node.put (node->get_ps_key (), node);
2919 /* Update per-program_point data. */
2920 per_point_data->m_enodes.safe_push (node);
2922 const enum point_kind node_pk = node->get_point ().get_kind ();
2923 m_global_stats.m_num_nodes[node_pk]++;
2924 per_fn_stats->m_num_nodes[node_pk]++;
2925 per_cs_stats->m_num_nodes[node_pk]++;
2927 if (node_pk == PK_AFTER_SUPERNODE)
2928 m_PK_AFTER_SUPERNODE_per_snode[point.get_supernode ()->m_index]++;
2933 pretty_printer *pp = logger->get_printer ();
2934 logger->log ("created EN: %i", node->m_index);
2935 logger->start_log_line ();
2936 pp_string (pp, "point: ");
2937 point.print (pp, f);
2938 logger->end_log_line ();
2939 logger->start_log_line ();
2940 pp_string (pp, "pruned_state: ");
2941 pruned_state.dump_to_pp (m_ext_state, true, false, pp);
2942 logger->end_log_line ();
2945 /* Add the new node to the worlist. */
2946 m_worklist.add_node (node);
2950 /* Add an exploded_edge from SRC to DEST, recording its association
2951 with SEDGE (which may be NULL), and, if non-NULL, taking ownership
2953 Return the newly-created eedge. */
2956 exploded_graph::add_edge (exploded_node *src, exploded_node *dest,
2957 const superedge *sedge,
2958 std::unique_ptr<custom_edge_info> custom_info)
2961 get_logger ()->log ("creating edge EN: %i -> EN: %i",
2962 src->m_index, dest->m_index);
2963 exploded_edge *e = new exploded_edge (src, dest, sedge,
2964 std::move (custom_info));
2965 digraph<eg_traits>::add_edge (e);
2969 /* Ensure that this graph has per-program_point-data for POINT;
2970 borrow a pointer to it. */
2972 per_program_point_data *
2974 get_or_create_per_program_point_data (const program_point &point)
2976 if (per_program_point_data **slot = m_per_point_data.get (&point))
2979 per_program_point_data *per_point_data = new per_program_point_data (point);
2980 m_per_point_data.put (&per_point_data->m_key, per_point_data);
2981 return per_point_data;
2984 /* Get this graph's per-program-point-data for POINT if there is any,
2987 per_program_point_data *
2988 exploded_graph::get_per_program_point_data (const program_point &point) const
2990 if (per_program_point_data **slot
2991 = const_cast <point_map_t &> (m_per_point_data).get (&point))
2997 /* Ensure that this graph has per-call_string-data for CS;
2998 borrow a pointer to it. */
3000 per_call_string_data *
3001 exploded_graph::get_or_create_per_call_string_data (const call_string &cs)
3003 if (per_call_string_data **slot = m_per_call_string_data.get (&cs))
3006 per_call_string_data *data = new per_call_string_data (cs, m_sg.num_nodes ());
3007 m_per_call_string_data.put (&data->m_key,
3012 /* Ensure that this graph has per-function-data for FUN;
3013 borrow a pointer to it. */
3016 exploded_graph::get_or_create_per_function_data (function *fun)
3018 if (per_function_data **slot = m_per_function_data.get (fun))
3021 per_function_data *data = new per_function_data ();
3022 m_per_function_data.put (fun, data);
3026 /* Get this graph's per-function-data for FUN if there is any,
3030 exploded_graph::get_per_function_data (function *fun) const
3032 if (per_function_data **slot
3033 = const_cast <per_function_data_t &> (m_per_function_data).get (fun))
3039 /* Return true if FUN should be traversed directly, rather than only as
3040 called via other functions. */
3043 toplevel_function_p (function *fun, logger *logger)
3045 /* Don't directly traverse into functions that have an "__analyzer_"
3046 prefix. Doing so is useful for the analyzer test suite, allowing
3047 us to have functions that are called in traversals, but not directly
3048 explored, thus testing how the analyzer handles calls and returns.
3049 With this, we can have DejaGnu directives that cover just the case
3050 of where a function is called by another function, without generating
3051 excess messages from the case of the first function being traversed
3053 #define ANALYZER_PREFIX "__analyzer_"
3054 if (!strncmp (IDENTIFIER_POINTER (DECL_NAME (fun->decl)), ANALYZER_PREFIX,
3055 strlen (ANALYZER_PREFIX)))
3058 logger->log ("not traversing %qE (starts with %qs)",
3059 fun->decl, ANALYZER_PREFIX);
3064 logger->log ("traversing %qE (all checks passed)", fun->decl);
3069 /* Custom event for use by tainted_call_info when a callback field has been
3070 marked with __attribute__((tainted_args)), for labelling the field. */
3072 class tainted_args_field_custom_event : public custom_event
3075 tainted_args_field_custom_event (tree field)
3076 : custom_event (event_loc_info (DECL_SOURCE_LOCATION (field), NULL_TREE, 0)),
3081 label_text get_desc (bool can_colorize) const final override
3083 return make_label_text (can_colorize,
3085 " is marked with %<__attribute__((tainted_args))%>",
3086 m_field, DECL_CONTEXT (m_field));
3093 /* Custom event for use by tainted_call_info when a callback field has been
3094 marked with __attribute__((tainted_args)), for labelling the function used
3095 in that callback. */
3097 class tainted_args_callback_custom_event : public custom_event
3100 tainted_args_callback_custom_event (const event_loc_info &loc_info,
3102 : custom_event (loc_info),
3107 label_text get_desc (bool can_colorize) const final override
3109 return make_label_text (can_colorize,
3110 "function %qE used as initializer for field %qE"
3111 " marked with %<__attribute__((tainted_args))%>",
3112 get_fndecl (), m_field);
3119 /* Custom edge info for use when adding a function used by a callback field
3120 marked with '__attribute__((tainted_args))'. */
3122 class tainted_args_call_info : public custom_edge_info
3125 tainted_args_call_info (tree field, tree fndecl, location_t loc)
3126 : m_field (field), m_fndecl (fndecl), m_loc (loc)
3129 void print (pretty_printer *pp) const final override
3131 pp_string (pp, "call to tainted field");
3134 bool update_model (region_model *,
3135 const exploded_edge *,
3136 region_model_context *) const final override
3142 void add_events_to_path (checker_path *emission_path,
3143 const exploded_edge &) const final override
3145 /* Show the field in the struct declaration, e.g.
3146 "(1) field 'store' is marked with '__attribute__((tainted_args))'" */
3147 emission_path->add_event
3148 (make_unique<tainted_args_field_custom_event> (m_field));
3150 /* Show the callback in the initializer
3152 "(2) function 'gadget_dev_desc_UDC_store' used as initializer
3153 for field 'store' marked with '__attribute__((tainted_args))'". */
3154 emission_path->add_event
3155 (make_unique<tainted_args_callback_custom_event>
3156 (event_loc_info (m_loc, m_fndecl, 0),
3166 /* Given an initializer at LOC for FIELD marked with
3167 '__attribute__((tainted_args))' initialized with FNDECL, add an
3168 entrypoint to FNDECL to EG (and to its worklist) where the params to
3169 FNDECL are marked as tainted. */
3172 add_tainted_args_callback (exploded_graph *eg, tree field, tree fndecl,
3175 logger *logger = eg->get_logger ();
3179 if (!gimple_has_body_p (fndecl))
3182 const extrinsic_state &ext_state = eg->get_ext_state ();
3184 function *fun = DECL_STRUCT_FUNCTION (fndecl);
3188 = program_point::from_function_entry (*ext_state.get_model_manager (),
3189 eg->get_supergraph (), fun);
3190 program_state state (ext_state);
3191 state.push_frame (ext_state, fun);
3193 if (!mark_params_as_tainted (&state, fndecl, ext_state))
3199 exploded_node *enode = eg->get_or_create_node (point, state, NULL);
3203 logger->log ("created EN %i for tainted_args %qE entrypoint",
3204 enode->m_index, fndecl);
3207 logger->log ("did not create enode for tainted_args %qE entrypoint",
3213 eg->add_edge (eg->get_origin (), enode, NULL,
3214 make_unique<tainted_args_call_info> (field, fndecl, loc));
3217 /* Callback for walk_tree for finding callbacks within initializers;
3218 ensure that any callback initializer where the corresponding field is
3219 marked with '__attribute__((tainted_args))' is treated as an entrypoint
3220 to the analysis, special-casing that the inputs to the callback are
3224 add_any_callbacks (tree *tp, int *, void *data)
3226 exploded_graph *eg = (exploded_graph *)data;
3227 if (TREE_CODE (*tp) == CONSTRUCTOR)
3229 /* Find fields with the "tainted_args" attribute.
3230 walk_tree only walks the values, not the index values;
3231 look at the index values. */
3232 unsigned HOST_WIDE_INT idx;
3233 constructor_elt *ce;
3235 for (idx = 0; vec_safe_iterate (CONSTRUCTOR_ELTS (*tp), idx, &ce);
3237 if (ce->index && TREE_CODE (ce->index) == FIELD_DECL)
3238 if (lookup_attribute ("tainted_args", DECL_ATTRIBUTES (ce->index)))
3240 tree value = ce->value;
3241 if (TREE_CODE (value) == ADDR_EXPR
3242 && TREE_CODE (TREE_OPERAND (value, 0)) == FUNCTION_DECL)
3243 add_tainted_args_callback (eg, ce->index,
3244 TREE_OPERAND (value, 0),
3245 EXPR_LOCATION (value));
3252 /* Add initial nodes to EG, with entrypoints for externally-callable
3256 exploded_graph::build_initial_worklist ()
3258 logger * const logger = get_logger ();
3262 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
3264 function *fun = node->get_fun ();
3265 if (!toplevel_function_p (fun, logger))
3267 exploded_node *enode = add_function_entry (fun);
3271 logger->log ("created EN %i for %qE entrypoint",
3272 enode->m_index, fun->decl);
3274 logger->log ("did not create enode for %qE entrypoint", fun->decl);
3278 /* Find callbacks that are reachable from global initializers. */
3279 varpool_node *vpnode;
3280 FOR_EACH_VARIABLE (vpnode)
3282 tree decl = vpnode->decl;
3283 tree init = DECL_INITIAL (decl);
3286 walk_tree (&init, add_any_callbacks, this, NULL);
3290 /* The main loop of the analysis.
3291 Take freshly-created exploded_nodes from the worklist, calling
3292 process_node on them to explore the <point, state> graph.
3293 Add edges to their successors, potentially creating new successors
3294 (which are also added to the worklist). */
3297 exploded_graph::process_worklist ()
3299 logger * const logger = get_logger ();
3301 auto_timevar tv (TV_ANALYZER_WORKLIST);
3303 while (m_worklist.length () > 0)
3305 exploded_node *node = m_worklist.take_next ();
3306 gcc_assert (node->get_status () == exploded_node::STATUS_WORKLIST);
3307 gcc_assert (node->m_succs.length () == 0
3308 || node == m_origin);
3311 logger->log ("next to process: EN: %i", node->m_index);
3313 /* If we have a run of nodes that are before-supernode, try merging and
3314 processing them together, rather than pairwise or individually. */
3315 if (flag_analyzer_state_merge && node != m_origin)
3316 if (maybe_process_run_of_before_supernode_enodes (node))
3319 /* Avoid exponential explosions of nodes by attempting to merge
3320 nodes that are at the same program point and which have
3321 sufficiently similar state. */
3322 if (flag_analyzer_state_merge && node != m_origin)
3323 if (exploded_node *node_2 = m_worklist.peek_next ())
3325 gcc_assert (node_2->get_status ()
3326 == exploded_node::STATUS_WORKLIST);
3327 gcc_assert (node->m_succs.length () == 0);
3328 gcc_assert (node_2->m_succs.length () == 0);
3330 gcc_assert (node != node_2);
3333 logger->log ("peek worklist: EN: %i", node_2->m_index);
3335 if (node->get_point () == node_2->get_point ())
3337 const program_point &point = node->get_point ();
3341 pretty_printer *pp = logger->get_printer ();
3342 logger->start_log_line ();
3344 ("got potential merge EN: %i and EN: %i at ",
3345 node->m_index, node_2->m_index);
3346 point.print (pp, f);
3347 logger->end_log_line ();
3349 const program_state &state = node->get_state ();
3350 const program_state &state_2 = node_2->get_state ();
3352 /* They shouldn't be equal, or we wouldn't have two
3354 gcc_assert (state != state_2);
3356 program_state merged_state (m_ext_state);
3357 if (state.can_merge_with_p (state_2, m_ext_state,
3358 point, &merged_state))
3361 logger->log ("merging EN: %i and EN: %i",
3362 node->m_index, node_2->m_index);
3364 if (merged_state == state)
3366 /* Then merge node_2 into node by adding an edge. */
3367 add_edge (node_2, node, NULL);
3369 /* Remove node_2 from the worklist. */
3370 m_worklist.take_next ();
3371 node_2->set_status (exploded_node::STATUS_MERGER);
3373 /* Continue processing "node" below. */
3375 else if (merged_state == state_2)
3377 /* Then merge node into node_2, and leave node_2
3378 in the worklist, to be processed on the next
3380 add_edge (node, node_2, NULL);
3381 node->set_status (exploded_node::STATUS_MERGER);
3386 /* We have a merged state that differs from
3387 both state and state_2. */
3389 /* Remove node_2 from the worklist. */
3390 m_worklist.take_next ();
3392 /* Create (or get) an exploded node for the merged
3393 states, adding to the worklist. */
3394 exploded_node *merged_enode
3395 = get_or_create_node (node->get_point (),
3396 merged_state, node);
3397 if (merged_enode == NULL)
3401 logger->log ("merged EN: %i and EN: %i into EN: %i",
3402 node->m_index, node_2->m_index,
3403 merged_enode->m_index);
3405 /* "node" and "node_2" have both now been removed
3406 from the worklist; we should not process them.
3408 "merged_enode" may be a new node; if so it will be
3409 processed in a subsequent iteration.
3410 Alternatively, "merged_enode" could be an existing
3411 node; one way the latter can
3412 happen is if we end up merging a succession of
3413 similar nodes into one. */
3415 /* If merged_node is one of the two we were merging,
3416 add it back to the worklist to ensure it gets
3419 Add edges from the merged nodes to it (but not a
3421 if (merged_enode == node)
3422 m_worklist.add_node (merged_enode);
3425 add_edge (node, merged_enode, NULL);
3426 node->set_status (exploded_node::STATUS_MERGER);
3429 if (merged_enode == node_2)
3430 m_worklist.add_node (merged_enode);
3433 add_edge (node_2, merged_enode, NULL);
3434 node_2->set_status (exploded_node::STATUS_MERGER);
3441 /* TODO: should we attempt more than two nodes,
3442 or just do pairs of nodes? (and hope that we get
3443 a cascade of mergers). */
3447 process_node (node);
3450 /* Impose a hard limit on the number of exploded nodes, to ensure
3451 that the analysis terminates in the face of pathological state
3452 explosion (or bugs).
3454 Specifically, the limit is on the number of PK_AFTER_SUPERNODE
3455 exploded nodes, looking at supernode exit events.
3457 We use exit rather than entry since there can be multiple
3458 entry ENs, one per phi; the number of PK_AFTER_SUPERNODE ought
3459 to be equivalent to the number of supernodes multiplied by the
3460 number of states. */
3461 const int limit = m_sg.num_nodes () * param_analyzer_bb_explosion_factor;
3462 if (m_global_stats.m_num_nodes[PK_AFTER_SUPERNODE] > limit)
3465 logger->log ("bailing out; too many nodes");
3466 warning_at (node->get_point ().get_location (),
3467 OPT_Wanalyzer_too_complex,
3468 "analysis bailed out early"
3469 " (%i 'after-snode' enodes; %i enodes)",
3470 m_global_stats.m_num_nodes[PK_AFTER_SUPERNODE],
3477 /* Attempt to process a consecutive run of sufficiently-similar nodes in
3478 the worklist at a CFG join-point (having already popped ENODE from the
3479 head of the worklist).
3481 If ENODE's point is of the form (before-supernode, SNODE) and the next
3482 nodes in the worklist are a consecutive run of enodes of the same form,
3483 for the same supernode as ENODE (but potentially from different in-edges),
3484 process them all together, setting their status to STATUS_BULK_MERGED,
3486 Otherwise, return false, in which case ENODE must be processed in the
3489 When processing them all together, generate successor states based
3490 on phi nodes for the appropriate CFG edges, and then attempt to merge
3491 these states into a minimal set of merged successor states, partitioning
3492 the inputs by merged successor state.
3494 Create new exploded nodes for all of the merged states, and add edges
3495 connecting the input enodes to the corresponding merger exploded nodes.
3497 We hope we have a much smaller number of merged successor states
3498 compared to the number of input enodes - ideally just one,
3499 if all successor states can be merged.
3501 Processing and merging many together as one operation rather than as
3502 pairs avoids scaling issues where per-pair mergers could bloat the
3503 graph with merger nodes (especially so after switch statements). */
3507 maybe_process_run_of_before_supernode_enodes (exploded_node *enode)
3509 /* A struct for tracking per-input state. */
3512 item (exploded_node *input_enode)
3513 : m_input_enode (input_enode),
3514 m_processed_state (input_enode->get_state ()),
3518 exploded_node *m_input_enode;
3519 program_state m_processed_state;
3523 gcc_assert (enode->get_status () == exploded_node::STATUS_WORKLIST);
3524 gcc_assert (enode->m_succs.length () == 0);
3526 const program_point &point = enode->get_point ();
3528 if (point.get_kind () != PK_BEFORE_SUPERNODE)
3531 const supernode *snode = point.get_supernode ();
3533 logger * const logger = get_logger ();
3536 /* Find a run of enodes in the worklist that are before the same supernode,
3537 but potentially from different in-edges. */
3538 auto_vec <exploded_node *> enodes;
3539 enodes.safe_push (enode);
3540 while (exploded_node *enode_2 = m_worklist.peek_next ())
3542 gcc_assert (enode_2->get_status ()
3543 == exploded_node::STATUS_WORKLIST);
3544 gcc_assert (enode_2->m_succs.length () == 0);
3546 const program_point &point_2 = enode_2->get_point ();
3548 if (point_2.get_kind () == PK_BEFORE_SUPERNODE
3549 && point_2.get_supernode () == snode
3550 && &point_2.get_call_string () == &point.get_call_string ())
3552 enodes.safe_push (enode_2);
3553 m_worklist.take_next ();
3559 /* If the only node is ENODE, then give up. */
3560 if (enodes.length () == 1)
3564 logger->log ("got run of %i enodes for SN: %i",
3565 enodes.length (), snode->m_index);
3567 /* All of these enodes have a shared successor point (even if they
3568 were for different in-edges). */
3569 program_point next_point (point.get_next ());
3571 /* Calculate the successor state for each enode in enodes. */
3572 auto_delete_vec<item> items (enodes.length ());
3574 exploded_node *iter_enode;
3575 FOR_EACH_VEC_ELT (enodes, i, iter_enode)
3577 item *it = new item (iter_enode);
3578 items.quick_push (it);
3579 const program_state &state = iter_enode->get_state ();
3580 program_state *next_state = &it->m_processed_state;
3581 next_state->validate (m_ext_state);
3582 const program_point &iter_point = iter_enode->get_point ();
3583 if (const superedge *iter_sedge = iter_point.get_from_edge ())
3585 uncertainty_t uncertainty;
3586 impl_region_model_context ctxt (*this, iter_enode,
3588 &uncertainty, NULL, NULL);
3589 const cfg_superedge *last_cfg_superedge
3590 = iter_sedge->dyn_cast_cfg_superedge ();
3591 if (last_cfg_superedge)
3592 next_state->m_region_model->update_for_phis
3593 (snode, last_cfg_superedge, &ctxt);
3595 next_state->validate (m_ext_state);
3598 /* Attempt to partition the items into a set of merged states.
3599 We hope we have a much smaller number of merged states
3600 compared to the number of input enodes - ideally just one,
3601 if all can be merged. */
3602 auto_delete_vec <program_state> merged_states;
3603 auto_vec<item *> first_item_for_each_merged_state;
3605 FOR_EACH_VEC_ELT (items, i, it)
3607 const program_state &it_state = it->m_processed_state;
3608 program_state *merged_state;
3609 unsigned iter_merger_idx;
3610 FOR_EACH_VEC_ELT (merged_states, iter_merger_idx, merged_state)
3612 merged_state->validate (m_ext_state);
3613 program_state merge (m_ext_state);
3614 if (it_state.can_merge_with_p (*merged_state, m_ext_state,
3615 next_point, &merge))
3617 *merged_state = merge;
3618 merged_state->validate (m_ext_state);
3619 it->m_merger_idx = iter_merger_idx;
3621 logger->log ("reusing merger state %i for item %i (EN: %i)",
3622 it->m_merger_idx, i, it->m_input_enode->m_index);
3626 /* If it couldn't be merged with any existing merged_states,
3627 create a new one. */
3628 if (it->m_merger_idx == -1)
3630 it->m_merger_idx = merged_states.length ();
3631 merged_states.safe_push (new program_state (it_state));
3632 first_item_for_each_merged_state.safe_push (it);
3634 logger->log ("using new merger state %i for item %i (EN: %i)",
3635 it->m_merger_idx, i, it->m_input_enode->m_index);
3638 gcc_assert (it->m_merger_idx >= 0);
3639 gcc_assert ((unsigned)it->m_merger_idx < merged_states.length ());
3642 /* Create merger nodes. */
3643 auto_vec<exploded_node *> next_enodes (merged_states.length ());
3644 program_state *merged_state;
3645 FOR_EACH_VEC_ELT (merged_states, i, merged_state)
3647 exploded_node *src_enode
3648 = first_item_for_each_merged_state[i]->m_input_enode;
3650 = get_or_create_node (next_point, *merged_state, src_enode);
3651 /* "next" could be NULL; we handle that when adding the edges below. */
3652 next_enodes.quick_push (next);
3656 logger->log ("using EN: %i for merger state %i", next->m_index, i);
3658 logger->log ("using NULL enode for merger state %i", i);
3662 /* Create edges from each input enode to the appropriate successor enode.
3663 Update the status of the now-processed input enodes. */
3664 FOR_EACH_VEC_ELT (items, i, it)
3666 exploded_node *next = next_enodes[it->m_merger_idx];
3668 add_edge (it->m_input_enode, next, NULL);
3669 it->m_input_enode->set_status (exploded_node::STATUS_BULK_MERGED);
3673 logger->log ("merged %i in-enodes into %i out-enode(s) at SN: %i",
3674 items.length (), merged_states.length (), snode->m_index);
3679 /* Return true if STMT must appear at the start of its exploded node, and
3680 thus we can't consolidate its effects within a run of other statements,
3681 where PREV_STMT was the previous statement. */
3684 stmt_requires_new_enode_p (const gimple *stmt,
3685 const gimple *prev_stmt)
3687 if (const gcall *call = dyn_cast <const gcall *> (stmt))
3689 /* Stop consolidating at calls to
3690 "__analyzer_dump_exploded_nodes", so they always appear at the
3691 start of an exploded_node. */
3692 if (is_special_named_call_p (call, "__analyzer_dump_exploded_nodes",
3696 /* sm-signal.cc injects an additional custom eedge at "signal" calls
3697 from the registration enode to the handler enode, separate from the
3698 regular next state, which defeats the "detect state change" logic
3699 in process_node. Work around this via special-casing, to ensure
3700 we split the enode immediately before any "signal" call. */
3701 if (is_special_named_call_p (call, "signal", 2))
3705 /* If we had a PREV_STMT with an unknown location, and this stmt
3706 has a known location, then if a state change happens here, it
3707 could be consolidated into PREV_STMT, giving us an event with
3708 no location. Ensure that STMT gets its own exploded_node to
3710 if (get_pure_location (prev_stmt->location) == UNKNOWN_LOCATION
3711 && get_pure_location (stmt->location) != UNKNOWN_LOCATION)
3717 /* Return true if OLD_STATE and NEW_STATE are sufficiently different that
3718 we should split enodes and create an exploded_edge separating them
3719 (which makes it easier to identify state changes of intereset when
3720 constructing checker_paths). */
3723 state_change_requires_new_enode_p (const program_state &old_state,
3724 const program_state &new_state)
3726 /* Changes in dynamic extents signify creations of heap/alloca regions
3727 and resizings of heap regions; likely to be of interest in
3728 diagnostic paths. */
3729 if (old_state.m_region_model->get_dynamic_extents ()
3730 != new_state.m_region_model->get_dynamic_extents ())
3733 /* Changes in sm-state are of interest. */
3736 FOR_EACH_VEC_ELT (old_state.m_checker_states, sm_idx, smap)
3738 const sm_state_map *old_smap = old_state.m_checker_states[sm_idx];
3739 const sm_state_map *new_smap = new_state.m_checker_states[sm_idx];
3740 if (*old_smap != *new_smap)
3747 /* Create enodes and eedges for the function calls that doesn't have an
3748 underlying call superedge.
3750 Such case occurs when GCC's middle end didn't know which function to
3751 call but the analyzer does (with the help of current state).
3753 Some example such calls are dynamically dispatched calls to virtual
3754 functions or calls that happen via function pointer. */
3757 exploded_graph::maybe_create_dynamic_call (const gcall *call,
3759 exploded_node *node,
3760 program_state next_state,
3761 program_point &next_point,
3762 uncertainty_t *uncertainty,
3767 const program_point *this_point = &node->get_point ();
3768 function *fun = DECL_STRUCT_FUNCTION (fn_decl);
3771 const supergraph &sg = this->get_supergraph ();
3772 supernode *sn_entry = sg.get_node_for_function_entry (fun);
3773 supernode *sn_exit = sg.get_node_for_function_exit (fun);
3775 program_point new_point
3776 = program_point::before_supernode (sn_entry,
3778 this_point->get_call_string ());
3780 new_point.push_to_call_stack (sn_exit,
3781 next_point.get_supernode());
3783 /* Impose a maximum recursion depth and don't analyze paths
3784 that exceed it further.
3785 This is something of a blunt workaround, but it only
3786 applies to recursion (and mutual recursion), not to
3787 general call stacks. */
3788 if (new_point.get_call_string ().calc_recursion_depth ()
3789 > param_analyzer_max_recursion_depth)
3792 logger->log ("rejecting call edge: recursion limit exceeded");
3796 next_state.push_call (*this, node, call, uncertainty);
3798 if (next_state.m_valid)
3801 logger->log ("Discovered call to %s [SN: %i -> SN: %i]",
3803 this_point->get_supernode ()->m_index,
3806 exploded_node *enode = get_or_create_node (new_point,
3810 add_edge (node,enode, NULL,
3811 make_unique<dynamic_call_info_t> (call));
3818 /* Subclass of path_context for use within exploded_graph::process_node,
3819 so that we can split states e.g. at "realloc" calls. */
3821 class impl_path_context : public path_context
3824 impl_path_context (const program_state *cur_state)
3825 : m_cur_state (cur_state),
3826 m_terminate_path (false)
3830 bool bifurcation_p () const
3832 return m_custom_eedge_infos.length () > 0;
3835 const program_state &get_state_at_bifurcation () const
3837 gcc_assert (m_state_at_bifurcation);
3838 return *m_state_at_bifurcation;
3842 bifurcate (std::unique_ptr<custom_edge_info> info) final override
3844 if (m_state_at_bifurcation)
3845 /* Verify that the state at bifurcation is consistent when we
3846 split into multiple out-edges. */
3847 gcc_assert (*m_state_at_bifurcation == *m_cur_state);
3849 /* Take a copy of the cur_state at the moment when bifurcation
3851 m_state_at_bifurcation
3852 = std::unique_ptr<program_state> (new program_state (*m_cur_state));
3854 /* Take ownership of INFO. */
3855 m_custom_eedge_infos.safe_push (info.release ());
3858 void terminate_path () final override
3860 m_terminate_path = true;
3863 bool terminate_path_p () const final override
3865 return m_terminate_path;
3868 const vec<custom_edge_info *> & get_custom_eedge_infos ()
3870 return m_custom_eedge_infos;
3874 const program_state *m_cur_state;
3876 /* Lazily-created copy of the state before the split. */
3877 std::unique_ptr<program_state> m_state_at_bifurcation;
3879 auto_vec <custom_edge_info *> m_custom_eedge_infos;
3881 bool m_terminate_path;
3884 /* A subclass of pending_diagnostic for complaining about jumps through NULL
3885 function pointers. */
3887 class jump_through_null : public pending_diagnostic_subclass<jump_through_null>
3890 jump_through_null (const gcall *call)
3894 const char *get_kind () const final override
3896 return "jump_through_null";
3899 bool operator== (const jump_through_null &other) const
3901 return m_call == other.m_call;
3904 int get_controlling_option () const final override
3906 return OPT_Wanalyzer_jump_through_null;
3909 bool emit (rich_location *rich_loc) final override
3911 return warning_at (rich_loc, get_controlling_option (),
3912 "jump through null pointer");
3915 label_text describe_final_event (const evdesc::final_event &ev) final override
3917 return ev.formatted_print ("jump through null pointer here");
3921 const gcall *m_call;
3924 /* The core of exploded_graph::process_worklist (the main analysis loop),
3925 handling one node in the worklist.
3927 Get successor <point, state> pairs for NODE, calling get_or_create on
3928 them, and adding an exploded_edge to each successors.
3930 Freshly-created nodes will be added to the worklist. */
3933 exploded_graph::process_node (exploded_node *node)
3935 logger * const logger = get_logger ();
3936 LOG_FUNC_1 (logger, "EN: %i", node->m_index);
3938 node->set_status (exploded_node::STATUS_PROCESSED);
3940 const program_point &point = node->get_point ();
3942 /* Update cfun and input_location in case of an ICE: make it easier to
3943 track down which source construct we're failing to handle. */
3944 auto_cfun sentinel (node->get_function ());
3945 const gimple *stmt = point.get_stmt ();
3947 input_location = stmt->location;
3949 const program_state &state = node->get_state ();
3952 pretty_printer *pp = logger->get_printer ();
3953 logger->start_log_line ();
3954 pp_string (pp, "point: ");
3955 point.print (pp, format (false));
3956 pp_string (pp, ", state: ");
3957 state.dump_to_pp (m_ext_state, true, false, pp);
3958 logger->end_log_line ();
3961 switch (point.get_kind ())
3966 /* This node exists to simplify finding the shortest path
3967 to an exploded_node. */
3970 case PK_BEFORE_SUPERNODE:
3972 program_state next_state (state);
3973 uncertainty_t uncertainty;
3975 if (point.get_from_edge ())
3977 impl_region_model_context ctxt (*this, node,
3978 &state, &next_state,
3979 &uncertainty, NULL, NULL);
3980 const cfg_superedge *last_cfg_superedge
3981 = point.get_from_edge ()->dyn_cast_cfg_superedge ();
3982 if (last_cfg_superedge)
3983 next_state.m_region_model->update_for_phis
3984 (node->get_supernode (),
3987 program_state::detect_leaks (state, next_state, NULL,
3988 get_ext_state (), &ctxt);
3991 program_point next_point (point.get_next ());
3992 exploded_node *next = get_or_create_node (next_point, next_state, node);
3994 add_edge (node, next, NULL);
3997 case PK_BEFORE_STMT:
3999 /* Determine the effect of a run of one or more statements
4000 within one supernode, generating an edge to the program_point
4001 after the last statement that's processed.
4003 Stop iterating statements and thus consolidating into one enode
4005 - reaching the end of the statements in the supernode
4006 - if an sm-state-change occurs (so that it gets its own
4008 - if "-fanalyzer-fine-grained" is active
4009 - encountering certain statements must appear at the start of
4010 their enode (for which stmt_requires_new_enode_p returns true)
4012 Update next_state in-place, to get the result of the one
4013 or more stmts that are processed.
4015 Split the node in-place if an sm-state-change occurs, so that
4016 the sm-state-change occurs on an edge where the src enode has
4017 exactly one stmt, the one that caused the change. */
4018 program_state next_state (state);
4020 impl_path_context path_ctxt (&next_state);
4022 uncertainty_t uncertainty;
4023 const supernode *snode = point.get_supernode ();
4025 const gimple *prev_stmt = NULL;
4026 for (stmt_idx = point.get_stmt_idx ();
4027 stmt_idx < snode->m_stmts.length ();
4030 const gimple *stmt = snode->m_stmts[stmt_idx];
4032 if (stmt_idx > point.get_stmt_idx ())
4033 if (stmt_requires_new_enode_p (stmt, prev_stmt))
4040 program_state old_state (next_state);
4042 /* Process the stmt. */
4043 exploded_node::on_stmt_flags flags
4044 = node->on_stmt (*this, snode, stmt, &next_state, &uncertainty,
4046 node->m_num_processed_stmts++;
4048 /* If flags.m_terminate_path, stop analyzing; any nodes/edges
4049 will have been added by on_stmt (e.g. for handling longjmp). */
4050 if (flags.m_terminate_path)
4053 if (next_state.m_region_model)
4055 impl_region_model_context ctxt (*this, node,
4056 &old_state, &next_state,
4057 &uncertainty, NULL, stmt);
4058 program_state::detect_leaks (old_state, next_state, NULL,
4059 get_ext_state (), &ctxt);
4062 unsigned next_idx = stmt_idx + 1;
4063 program_point next_point
4064 = (next_idx < point.get_supernode ()->m_stmts.length ()
4065 ? program_point::before_stmt (point.get_supernode (), next_idx,
4066 point.get_call_string ())
4067 : program_point::after_supernode (point.get_supernode (),
4068 point.get_call_string ()));
4069 next_state = next_state.prune_for_point (*this, next_point, node,
4072 if (flag_analyzer_fine_grained
4073 || state_change_requires_new_enode_p (old_state, next_state)
4074 || path_ctxt.bifurcation_p ()
4075 || path_ctxt.terminate_path_p ())
4077 program_point split_point
4078 = program_point::before_stmt (point.get_supernode (),
4080 point.get_call_string ());
4081 if (split_point != node->get_point ())
4083 /* If we're not at the start of NODE, split the enode at
4084 this stmt, so we have:
4086 so that when split_enode is processed the next edge
4089 and any state change will effectively occur on that
4090 latter edge, and split_enode will contain just stmt. */
4092 logger->log ("getting split_enode");
4093 exploded_node *split_enode
4094 = get_or_create_node (split_point, old_state, node);
4097 /* "stmt" will be reprocessed when split_enode is
4099 node->m_num_processed_stmts--;
4101 logger->log ("creating edge to split_enode");
4102 add_edge (node, split_enode, NULL);
4106 /* If we're at the start of NODE, stop iterating,
4107 so that an edge will be created from NODE to
4108 (next_point, next_state) below. */
4112 unsigned next_idx = stmt_idx + 1;
4113 program_point next_point
4114 = (next_idx < point.get_supernode ()->m_stmts.length ()
4115 ? program_point::before_stmt (point.get_supernode (), next_idx,
4116 point.get_call_string ())
4117 : program_point::after_supernode (point.get_supernode (),
4118 point.get_call_string ()));
4119 if (path_ctxt.terminate_path_p ())
4122 logger->log ("not adding node: terminating path");
4127 = get_or_create_node (next_point, next_state, node);
4129 add_edge (node, next, NULL);
4132 /* If we have custom edge infos, "bifurcate" the state
4133 accordingly, potentially creating a new state/enode/eedge
4134 instances. For example, to handle a "realloc" call, we
4135 might split into 3 states, for the "failure",
4136 "resizing in place", and "moving to a new buffer" cases. */
4137 for (auto edge_info_iter : path_ctxt.get_custom_eedge_infos ())
4139 /* Take ownership of the edge infos from the path_ctxt. */
4140 std::unique_ptr<custom_edge_info> edge_info (edge_info_iter);
4143 logger->start_log_line ();
4144 logger->log_partial ("bifurcating for edge: ");
4145 edge_info->print (logger->get_printer ());
4146 logger->end_log_line ();
4148 program_state bifurcated_new_state
4149 (path_ctxt.get_state_at_bifurcation ());
4151 /* Apply edge_info to state. */
4152 impl_region_model_context
4153 bifurcation_ctxt (*this,
4154 node, // enode_for_diag
4155 &path_ctxt.get_state_at_bifurcation (),
4156 &bifurcated_new_state,
4157 NULL, // uncertainty_t *uncertainty
4158 NULL, // path_context *path_ctxt
4160 if (edge_info->update_state (&bifurcated_new_state,
4161 NULL, /* no exploded_edge yet. */
4164 exploded_node *next2
4165 = get_or_create_node (next_point, bifurcated_new_state, node);
4167 add_edge (node, next2, NULL, std::move (edge_info));
4172 logger->log ("infeasible state, not adding node");
4177 case PK_AFTER_SUPERNODE:
4179 bool found_a_superedge = false;
4180 bool is_an_exit_block = false;
4181 /* If this is an EXIT BB, detect leaks, and potentially
4182 create a function summary. */
4183 if (point.get_supernode ()->return_p ())
4185 is_an_exit_block = true;
4186 node->detect_leaks (*this);
4187 if (flag_analyzer_call_summaries
4188 && point.get_call_string ().empty_p ())
4190 /* TODO: create function summary
4191 There can be more than one; each corresponds to a different
4192 final enode in the function. */
4195 pretty_printer *pp = logger->get_printer ();
4196 logger->start_log_line ();
4198 ("would create function summary for %qE; state: ",
4199 point.get_fndecl ());
4200 state.dump_to_pp (m_ext_state, true, false, pp);
4201 logger->end_log_line ();
4203 per_function_data *per_fn_data
4204 = get_or_create_per_function_data (point.get_function ());
4205 per_fn_data->add_call_summary (node);
4208 /* Traverse into successors of the supernode. */
4211 FOR_EACH_VEC_ELT (point.get_supernode ()->m_succs, i, succ)
4213 found_a_superedge = true;
4216 label_text succ_desc (succ->get_description (false));
4217 logger->log ("considering SN: %i -> SN: %i (%s)",
4218 succ->m_src->m_index, succ->m_dest->m_index,
4222 program_point next_point
4223 = program_point::before_supernode (succ->m_dest, succ,
4224 point.get_call_string ());
4225 program_state next_state (state);
4226 uncertainty_t uncertainty;
4228 /* Make use the current state and try to discover and analyse
4229 indirect function calls (a call that doesn't have an underlying
4230 cgraph edge representing call).
4232 Some examples of such calls are virtual function calls
4233 and calls that happen via a function pointer. */
4234 if (succ->m_kind == SUPEREDGE_INTRAPROCEDURAL_CALL
4235 && !(succ->get_any_callgraph_edge ()))
4238 = point.get_supernode ()->get_final_call ();
4240 impl_region_model_context ctxt (*this,
4248 region_model *model = state.m_region_model;
4249 bool call_discovered = false;
4251 if (tree fn_decl = model->get_fndecl_for_call (call, &ctxt))
4252 call_discovered = maybe_create_dynamic_call (call,
4259 if (!call_discovered)
4261 /* Check for jump through NULL. */
4262 if (tree fn_ptr = gimple_call_fn (call))
4264 const svalue *fn_ptr_sval
4265 = model->get_rvalue (fn_ptr, &ctxt);
4266 if (fn_ptr_sval->all_zeroes_p ())
4267 ctxt.warn (make_unique<jump_through_null> (call));
4270 /* An unknown function or a special function was called
4271 at this point, in such case, don't terminate the
4272 analysis of the current function.
4274 The analyzer handles calls to such functions while
4275 analysing the stmt itself, so the function call
4276 must have been handled by the anlyzer till now. */
4278 = get_or_create_node (next_point,
4282 add_edge (node, next, succ);
4286 if (!node->on_edge (*this, succ, &next_point, &next_state,
4290 logger->log ("skipping impossible edge to SN: %i",
4291 succ->m_dest->m_index);
4294 exploded_node *next = get_or_create_node (next_point, next_state,
4298 add_edge (node, next, succ);
4300 /* We might have a function entrypoint. */
4301 detect_infinite_recursion (next);
4305 /* Return from the calls which doesn't have a return superedge.
4306 Such case occurs when GCC's middle end didn't knew which function to
4307 call but analyzer did. */
4308 if ((is_an_exit_block && !found_a_superedge)
4309 && (!point.get_call_string ().empty_p ()))
4311 const call_string &cs = point.get_call_string ();
4312 program_point next_point
4313 = program_point::before_supernode (cs.get_caller_node (),
4316 program_state next_state (state);
4317 uncertainty_t uncertainty;
4320 = next_point.get_supernode ()->get_returning_call ();
4323 next_state.returning_call (*this, node, call, &uncertainty);
4325 if (next_state.m_valid)
4327 next_point.pop_from_call_stack ();
4328 exploded_node *enode = get_or_create_node (next_point,
4332 add_edge (node, enode, NULL,
4333 make_unique<dynamic_call_info_t> (call, true));
4341 /* Ensure that this graph has a stats instance for FN, return it.
4342 FN can be NULL, in which case a stats instances is returned covering
4343 "functionless" parts of the graph (the origin node). */
4346 exploded_graph::get_or_create_function_stats (function *fn)
4349 return &m_functionless_stats;
4351 if (stats **slot = m_per_function_stats.get (fn))
4355 int num_supernodes = fn ? n_basic_blocks_for_fn (fn) : 0;
4356 /* not quite the num supernodes, but nearly. */
4357 stats *new_stats = new stats (num_supernodes);
4358 m_per_function_stats.put (fn, new_stats);
4363 /* Print bar charts to PP showing:
4364 - the number of enodes per function, and
4365 - for each function:
4366 - the number of enodes per supernode/BB
4367 - the number of excess enodes per supernode/BB beyond the
4368 per-program-point limit, if there were any. */
4371 exploded_graph::print_bar_charts (pretty_printer *pp) const
4373 cgraph_node *cgnode;
4375 pp_string (pp, "enodes per function:");
4377 bar_chart enodes_per_function;
4378 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode)
4380 function *fn = cgnode->get_fun ();
4381 const stats * const *s_ptr
4382 = const_cast <function_stat_map_t &> (m_per_function_stats).get (fn);
4383 enodes_per_function.add_item (function_name (fn),
4384 s_ptr ? (*s_ptr)->get_total_enodes () : 0);
4386 enodes_per_function.print (pp);
4388 /* Accumulate number of enodes per supernode. */
4389 auto_vec<unsigned> enodes_per_supernode (m_sg.num_nodes ());
4390 for (int i = 0; i < m_sg.num_nodes (); i++)
4391 enodes_per_supernode.quick_push (0);
4393 exploded_node *enode;
4394 FOR_EACH_VEC_ELT (m_nodes, i, enode)
4396 const supernode *iter_snode = enode->get_supernode ();
4399 enodes_per_supernode[iter_snode->m_index]++;
4402 /* Accumulate excess enodes per supernode. */
4403 auto_vec<unsigned> excess_enodes_per_supernode (m_sg.num_nodes ());
4404 for (int i = 0; i < m_sg.num_nodes (); i++)
4405 excess_enodes_per_supernode.quick_push (0);
4406 for (point_map_t::iterator iter = m_per_point_data.begin ();
4407 iter != m_per_point_data.end (); ++iter)
4409 const program_point *point = (*iter).first;
4410 const supernode *iter_snode = point->get_supernode ();
4413 const per_program_point_data *point_data = (*iter).second;
4414 excess_enodes_per_supernode[iter_snode->m_index]
4415 += point_data->m_excess_enodes;
4418 /* Show per-function bar_charts of enodes per supernode/BB. */
4419 pp_string (pp, "per-function enodes per supernode/BB:");
4421 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode)
4423 function *fn = cgnode->get_fun ();
4424 pp_printf (pp, "function: %qs", function_name (fn));
4427 bar_chart enodes_per_snode;
4428 bar_chart excess_enodes_per_snode;
4429 bool have_excess_enodes = false;
4430 for (int i = 0; i < m_sg.num_nodes (); i++)
4432 const supernode *iter_snode = m_sg.get_node_by_index (i);
4433 if (iter_snode->get_function () != fn)
4435 pretty_printer tmp_pp;
4436 pp_printf (&tmp_pp, "sn %i (bb %i)",
4437 iter_snode->m_index, iter_snode->m_bb->index);
4438 enodes_per_snode.add_item (pp_formatted_text (&tmp_pp),
4439 enodes_per_supernode[iter_snode->m_index]);
4440 const int num_excess
4441 = excess_enodes_per_supernode[iter_snode->m_index];
4442 excess_enodes_per_snode.add_item (pp_formatted_text (&tmp_pp),
4445 have_excess_enodes = true;
4447 enodes_per_snode.print (pp);
4448 if (have_excess_enodes)
4450 pp_printf (pp, "EXCESS ENODES:");
4452 excess_enodes_per_snode.print (pp);
4457 /* Write all stats information to this graph's logger, if any. */
4460 exploded_graph::log_stats () const
4462 logger * const logger = get_logger ();
4468 m_ext_state.get_engine ()->log_stats (logger);
4470 logger->log ("m_sg.num_nodes (): %i", m_sg.num_nodes ());
4471 logger->log ("m_nodes.length (): %i", m_nodes.length ());
4472 logger->log ("m_edges.length (): %i", m_edges.length ());
4473 logger->log ("remaining enodes in worklist: %i", m_worklist.length ());
4475 logger->log ("global stats:");
4476 m_global_stats.log (logger);
4478 for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
4479 iter != m_per_function_stats.end ();
4482 function *fn = (*iter).first;
4483 log_scope s (logger, function_name (fn));
4484 (*iter).second->log (logger);
4487 print_bar_charts (logger->get_printer ());
4490 /* Dump all stats information to OUT. */
4493 exploded_graph::dump_stats (FILE *out) const
4495 fprintf (out, "m_sg.num_nodes (): %i\n", m_sg.num_nodes ());
4496 fprintf (out, "m_nodes.length (): %i\n", m_nodes.length ());
4497 fprintf (out, "m_edges.length (): %i\n", m_edges.length ());
4498 fprintf (out, "remaining enodes in worklist: %i", m_worklist.length ());
4500 fprintf (out, "global stats:\n");
4501 m_global_stats.dump (out);
4503 for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
4504 iter != m_per_function_stats.end ();
4507 function *fn = (*iter).first;
4508 fprintf (out, "function: %s\n", function_name (fn));
4509 (*iter).second->dump (out);
4512 fprintf (out, "PK_AFTER_SUPERNODE per supernode:\n");
4513 for (unsigned i = 0; i < m_PK_AFTER_SUPERNODE_per_snode.length (); i++)
4514 fprintf (out, " SN %i: %3i\n", i, m_PK_AFTER_SUPERNODE_per_snode[i]);
4518 exploded_graph::dump_states_for_supernode (FILE *out,
4519 const supernode *snode) const
4521 fprintf (out, "PK_AFTER_SUPERNODE nodes for SN: %i\n", snode->m_index);
4523 exploded_node *enode;
4525 FOR_EACH_VEC_ELT (m_nodes, i, enode)
4527 const supernode *iter_snode = enode->get_supernode ();
4528 if (enode->get_point ().get_kind () == PK_AFTER_SUPERNODE
4529 && iter_snode == snode)
4532 pp_format_decoder (&pp) = default_tree_printer;
4533 enode->get_state ().dump_to_pp (m_ext_state, true, false, &pp);
4534 fprintf (out, "state %i: EN: %i\n %s\n",
4535 state_idx++, enode->m_index,
4536 pp_formatted_text (&pp));
4539 fprintf (out, "#exploded_node for PK_AFTER_SUPERNODE for SN: %i = %i\n",
4540 snode->m_index, state_idx);
4543 /* Return a new json::object of the form
4544 {"nodes" : [objs for enodes],
4545 "edges" : [objs for eedges],
4546 "ext_state": object for extrinsic_state,
4547 "diagnostic_manager": object for diagnostic_manager}. */
4550 exploded_graph::to_json () const
4552 json::object *egraph_obj = new json::object ();
4556 json::array *nodes_arr = new json::array ();
4559 FOR_EACH_VEC_ELT (m_nodes, i, n)
4560 nodes_arr->append (n->to_json (m_ext_state));
4561 egraph_obj->set ("nodes", nodes_arr);
4566 json::array *edges_arr = new json::array ();
4569 FOR_EACH_VEC_ELT (m_edges, i, n)
4570 edges_arr->append (n->to_json ());
4571 egraph_obj->set ("edges", edges_arr);
4574 /* m_sg is JSONified at the top-level. */
4576 egraph_obj->set ("ext_state", m_ext_state.to_json ());
4577 egraph_obj->set ("worklist", m_worklist.to_json ());
4578 egraph_obj->set ("diagnostic_manager", m_diagnostic_manager.to_json ());
4580 /* The following fields aren't yet being JSONified:
4581 const state_purge_map *const m_purge_map;
4582 const analysis_plan &m_plan;
4583 stats m_global_stats;
4584 function_stat_map_t m_per_function_stats;
4585 stats m_functionless_stats;
4586 call_string_data_map_t m_per_call_string_data;
4587 auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode; */
4592 /* class exploded_path. */
4596 exploded_path::exploded_path (const exploded_path &other)
4597 : m_edges (other.m_edges.length ())
4600 const exploded_edge *eedge;
4601 FOR_EACH_VEC_ELT (other.m_edges, i, eedge)
4602 m_edges.quick_push (eedge);
4605 /* Look for the last use of SEARCH_STMT within this path.
4606 If found write the edge's index to *OUT_IDX and return true, otherwise
4610 exploded_path::find_stmt_backwards (const gimple *search_stmt,
4614 const exploded_edge *eedge;
4615 FOR_EACH_VEC_ELT_REVERSE (m_edges, i, eedge)
4617 const exploded_node *dst_node = eedge->m_dest;
4618 const program_point &dst_point = dst_node->get_point ();
4619 const gimple *stmt = dst_point.get_stmt ();
4620 if (stmt == search_stmt)
4629 /* Get the final exploded_node in this path, which must be non-empty. */
4632 exploded_path::get_final_enode () const
4634 gcc_assert (m_edges.length () > 0);
4635 return m_edges[m_edges.length () - 1]->m_dest;
4638 /* Check state along this path, returning true if it is feasible.
4639 If OUT is non-NULL, and the path is infeasible, write a new
4640 feasibility_problem to *OUT. */
4643 exploded_path::feasible_p (logger *logger,
4644 std::unique_ptr<feasibility_problem> *out,
4645 engine *eng, const exploded_graph *eg) const
4649 feasibility_state state (eng->get_model_manager (),
4650 eg->get_supergraph ());
4652 /* Traverse the path, updating this state. */
4653 for (unsigned edge_idx = 0; edge_idx < m_edges.length (); edge_idx++)
4655 const exploded_edge *eedge = m_edges[edge_idx];
4657 logger->log ("considering edge %i: EN:%i -> EN:%i",
4659 eedge->m_src->m_index,
4660 eedge->m_dest->m_index);
4662 rejected_constraint *rc = NULL;
4663 if (!state.maybe_update_for_edge (logger, eedge, &rc))
4668 const exploded_node &src_enode = *eedge->m_src;
4669 const program_point &src_point = src_enode.get_point ();
4670 const gimple *last_stmt
4671 = src_point.get_supernode ()->get_last_stmt ();
4672 *out = make_unique<feasibility_problem> (edge_idx, *eedge,
4682 logger->log ("state after edge %i: EN:%i -> EN:%i",
4684 eedge->m_src->m_index,
4685 eedge->m_dest->m_index);
4686 logger->start_log_line ();
4687 state.get_model ().dump_to_pp (logger->get_printer (), true, false);
4688 logger->end_log_line ();
4695 /* Dump this path in multiline form to PP.
4696 If EXT_STATE is non-NULL, then show the nodes. */
4699 exploded_path::dump_to_pp (pretty_printer *pp,
4700 const extrinsic_state *ext_state) const
4702 for (unsigned i = 0; i < m_edges.length (); i++)
4704 const exploded_edge *eedge = m_edges[i];
4705 pp_printf (pp, "m_edges[%i]: EN %i -> EN %i",
4707 eedge->m_src->m_index,
4708 eedge->m_dest->m_index);
4712 eedge->m_dest->dump_to_pp (pp, *ext_state);
4716 /* Dump this path in multiline form to FP. */
4719 exploded_path::dump (FILE *fp, const extrinsic_state *ext_state) const
4722 pp_format_decoder (&pp) = default_tree_printer;
4723 pp_show_color (&pp) = pp_show_color (global_dc->printer);
4724 pp.buffer->stream = fp;
4725 dump_to_pp (&pp, ext_state);
4729 /* Dump this path in multiline form to stderr. */
4732 exploded_path::dump (const extrinsic_state *ext_state) const
4734 dump (stderr, ext_state);
4737 /* Dump this path verbosely to FILENAME. */
4740 exploded_path::dump_to_file (const char *filename,
4741 const extrinsic_state &ext_state) const
4743 FILE *fp = fopen (filename, "w");
4747 pp_format_decoder (&pp) = default_tree_printer;
4748 pp.buffer->stream = fp;
4749 dump_to_pp (&pp, &ext_state);
4754 /* class feasibility_problem. */
4757 feasibility_problem::dump_to_pp (pretty_printer *pp) const
4759 pp_printf (pp, "edge from EN: %i to EN: %i",
4760 m_eedge.m_src->m_index, m_eedge.m_dest->m_index);
4763 pp_string (pp, "; rejected constraint: ");
4764 m_rc->dump_to_pp (pp);
4765 pp_string (pp, "; rmodel: ");
4766 m_rc->get_model ().dump_to_pp (pp, true, false);
4770 /* class feasibility_state. */
4772 /* Ctor for feasibility_state, at the beginning of a path. */
4774 feasibility_state::feasibility_state (region_model_manager *manager,
4775 const supergraph &sg)
4776 : m_model (manager),
4777 m_snodes_visited (sg.m_nodes.length ())
4779 bitmap_clear (m_snodes_visited);
4782 /* Copy ctor for feasibility_state, for extending a path. */
4784 feasibility_state::feasibility_state (const feasibility_state &other)
4785 : m_model (other.m_model),
4786 m_snodes_visited (const_sbitmap (other.m_snodes_visited)->n_bits)
4788 bitmap_copy (m_snodes_visited, other.m_snodes_visited);
4791 /* The heart of feasibility-checking.
4793 Attempt to update this state in-place based on traversing EEDGE
4795 Update the model for the stmts in the src enode.
4796 Attempt to add constraints for EEDGE.
4798 If feasible, return true.
4799 Otherwise, return false and write to *OUT_RC. */
4802 feasibility_state::maybe_update_for_edge (logger *logger,
4803 const exploded_edge *eedge,
4804 rejected_constraint **out_rc)
4806 const exploded_node &src_enode = *eedge->m_src;
4807 const program_point &src_point = src_enode.get_point ();
4810 logger->start_log_line ();
4811 src_point.print (logger->get_printer (), format (false));
4812 logger->end_log_line ();
4815 /* Update state for the stmts that were processed in each enode. */
4816 for (unsigned stmt_idx = 0; stmt_idx < src_enode.m_num_processed_stmts;
4819 const gimple *stmt = src_enode.get_processed_stmt (stmt_idx);
4821 /* Update cfun and input_location in case of ICE: make it easier to
4822 track down which source construct we're failing to handle. */
4823 auto_cfun sentinel (src_point.get_function ());
4824 input_location = stmt->location;
4826 if (const gassign *assign = dyn_cast <const gassign *> (stmt))
4827 m_model.on_assignment (assign, NULL);
4828 else if (const gasm *asm_stmt = dyn_cast <const gasm *> (stmt))
4829 m_model.on_asm_stmt (asm_stmt, NULL);
4830 else if (const gcall *call = dyn_cast <const gcall *> (stmt))
4832 bool unknown_side_effects = m_model.on_call_pre (call, NULL);
4833 m_model.on_call_post (call, unknown_side_effects, NULL);
4835 else if (const greturn *return_ = dyn_cast <const greturn *> (stmt))
4836 m_model.on_return (return_, NULL);
4839 const superedge *sedge = eedge->m_sedge;
4844 label_text desc (sedge->get_description (false));
4845 logger->log (" sedge: SN:%i -> SN:%i %s",
4846 sedge->m_src->m_index,
4847 sedge->m_dest->m_index,
4851 const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt ();
4852 if (!m_model.maybe_update_for_edge (*sedge, last_stmt, NULL, out_rc))
4856 logger->log ("rejecting due to region model");
4857 m_model.dump_to_pp (logger->get_printer (), true, false);
4864 /* Special-case the initial eedge from the origin node to the
4865 initial function by pushing a frame for it. */
4866 if (src_point.get_kind () == PK_ORIGIN)
4868 gcc_assert (eedge->m_src->m_index == 0);
4869 gcc_assert (eedge->m_dest->get_point ().get_kind ()
4870 == PK_BEFORE_SUPERNODE);
4871 function *fun = eedge->m_dest->get_function ();
4873 m_model.push_frame (fun, NULL, NULL);
4875 logger->log (" pushing frame for %qD", fun->decl);
4877 else if (eedge->m_custom_info)
4879 eedge->m_custom_info->update_model (&m_model, eedge, NULL);
4883 /* Handle phi nodes on an edge leaving a PK_BEFORE_SUPERNODE (to
4884 a PK_BEFORE_STMT, or a PK_AFTER_SUPERNODE if no stmts).
4885 This will typically not be associated with a superedge. */
4886 if (src_point.get_from_edge ())
4888 const cfg_superedge *last_cfg_superedge
4889 = src_point.get_from_edge ()->dyn_cast_cfg_superedge ();
4890 const exploded_node &dst_enode = *eedge->m_dest;
4891 const unsigned dst_snode_idx = dst_enode.get_supernode ()->m_index;
4892 if (last_cfg_superedge)
4895 logger->log (" update for phis");
4896 m_model.update_for_phis (src_enode.get_supernode (),
4899 /* If we've entering an snode that we've already visited on this
4900 epath, then we need do fix things up for loops; see the
4901 comment for store::loop_replay_fixup.
4902 Perhaps we should probably also verify the callstring,
4903 and track program_points, but hopefully doing it by supernode
4905 if (bitmap_bit_p (m_snodes_visited, dst_snode_idx))
4906 m_model.loop_replay_fixup (dst_enode.get_state ().m_region_model);
4908 bitmap_set_bit (m_snodes_visited, dst_snode_idx);
4913 /* Dump this object to PP. */
4916 feasibility_state::dump_to_pp (pretty_printer *pp,
4917 bool simple, bool multiline) const
4919 m_model.dump_to_pp (pp, simple, multiline);
4922 /* A family of cluster subclasses for use when generating .dot output for
4923 exploded graphs (-fdump-analyzer-exploded-graph), for grouping the
4924 enodes into hierarchical boxes.
4926 All functionless enodes appear in the top-level graph.
4927 Every (function, call_string) pair gets its own cluster. Within that
4928 cluster, each supernode gets its own cluster.
4930 Hence all enodes relating to a particular function with a particular
4931 callstring will be in a cluster together; all enodes for the same
4932 function but with a different callstring will be in a different
4935 /* Base class of cluster for clustering exploded_node instances in .dot
4936 output, based on various subclass-specific criteria. */
4938 class exploded_cluster : public cluster<eg_traits>
4942 /* Cluster containing all exploded_node instances for one supernode. */
4944 class supernode_cluster : public exploded_cluster
4947 supernode_cluster (const supernode *supernode) : m_supernode (supernode) {}
4951 void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
4953 gv->println ("subgraph \"cluster_supernode_%i\" {", m_supernode->m_index);
4955 gv->println ("style=\"dashed\";");
4956 gv->println ("label=\"SN: %i (bb: %i; scc: %i)\";",
4957 m_supernode->m_index, m_supernode->m_bb->index,
4958 args.m_eg.get_scc_id (*m_supernode));
4961 exploded_node *enode;
4962 FOR_EACH_VEC_ELT (m_enodes, i, enode)
4963 enode->dump_dot (gv, args);
4965 /* Terminate subgraph. */
4970 void add_node (exploded_node *en) final override
4972 m_enodes.safe_push (en);
4975 /* Comparator for use by auto_vec<supernode_cluster *>::qsort. */
4977 static int cmp_ptr_ptr (const void *p1, const void *p2)
4979 const supernode_cluster *c1
4980 = *(const supernode_cluster * const *)p1;
4981 const supernode_cluster *c2
4982 = *(const supernode_cluster * const *)p2;
4983 return c1->m_supernode->m_index - c2->m_supernode->m_index;
4987 const supernode *m_supernode;
4988 auto_vec <exploded_node *> m_enodes;
4991 /* Cluster containing all supernode_cluster instances for one
4992 (function, call_string) pair. */
4994 class function_call_string_cluster : public exploded_cluster
4997 function_call_string_cluster (function *fun, const call_string &cs)
4998 : m_fun (fun), m_cs (cs) {}
5000 ~function_call_string_cluster ()
5002 for (map_t::iterator iter = m_map.begin ();
5003 iter != m_map.end ();
5005 delete (*iter).second;
5008 void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
5010 const char *funcname = function_name (m_fun);
5012 gv->println ("subgraph \"cluster_function_%s\" {",
5013 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (m_fun->decl)));
5015 gv->write_indent ();
5016 gv->print ("label=\"call string: ");
5017 m_cs.print (gv->get_pp ());
5018 gv->print (" function: %s \";", funcname);
5021 /* Dump m_map, sorting it to avoid churn when comparing dumps. */
5022 auto_vec<supernode_cluster *> child_clusters (m_map.elements ());
5023 for (map_t::iterator iter = m_map.begin ();
5024 iter != m_map.end ();
5026 child_clusters.quick_push ((*iter).second);
5028 child_clusters.qsort (supernode_cluster::cmp_ptr_ptr);
5031 supernode_cluster *child_cluster;
5032 FOR_EACH_VEC_ELT (child_clusters, i, child_cluster)
5033 child_cluster->dump_dot (gv, args);
5035 /* Terminate subgraph. */
5040 void add_node (exploded_node *en) final override
5042 const supernode *supernode = en->get_supernode ();
5043 gcc_assert (supernode);
5044 supernode_cluster **slot = m_map.get (supernode);
5046 (*slot)->add_node (en);
5049 supernode_cluster *child = new supernode_cluster (supernode);
5050 m_map.put (supernode, child);
5051 child->add_node (en);
5055 /* Comparator for use by auto_vec<function_call_string_cluster *>. */
5057 static int cmp_ptr_ptr (const void *p1, const void *p2)
5059 const function_call_string_cluster *c1
5060 = *(const function_call_string_cluster * const *)p1;
5061 const function_call_string_cluster *c2
5062 = *(const function_call_string_cluster * const *)p2;
5064 = strcmp (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c1->m_fun->decl)),
5065 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c2->m_fun->decl))))
5067 return call_string::cmp (c1->m_cs, c2->m_cs);
5072 const call_string &m_cs;
5073 typedef ordered_hash_map<const supernode *, supernode_cluster *> map_t;
5077 /* Keys for root_cluster. */
5079 struct function_call_string
5081 function_call_string (function *fun, const call_string *cs)
5082 : m_fun (fun), m_cs (cs)
5089 const call_string *m_cs;
5094 template <> struct default_hash_traits<function_call_string>
5095 : public pod_hash_traits<function_call_string>
5097 static const bool empty_zero_p = false;
5102 pod_hash_traits<function_call_string>::hash (value_type v)
5104 return (pointer_hash <function>::hash (v.m_fun)
5105 ^ pointer_hash <const call_string>::hash (v.m_cs));
5110 pod_hash_traits<function_call_string>::equal (const value_type &existing,
5111 const value_type &candidate)
5113 return existing.m_fun == candidate.m_fun && &existing.m_cs == &candidate.m_cs;
5117 pod_hash_traits<function_call_string>::mark_deleted (value_type &v)
5119 v.m_fun = reinterpret_cast<function *> (1);
5123 pod_hash_traits<function_call_string>::mark_empty (value_type &v)
5129 pod_hash_traits<function_call_string>::is_deleted (value_type v)
5131 return v.m_fun == reinterpret_cast<function *> (1);
5135 pod_hash_traits<function_call_string>::is_empty (value_type v)
5137 return v.m_fun == NULL;
5142 /* Top-level cluster for generating .dot output for exploded graphs,
5143 handling the functionless nodes, and grouping the remaining nodes by
5146 class root_cluster : public exploded_cluster
5151 for (map_t::iterator iter = m_map.begin ();
5152 iter != m_map.end ();
5154 delete (*iter).second;
5157 void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
5160 exploded_node *enode;
5161 FOR_EACH_VEC_ELT (m_functionless_enodes, i, enode)
5162 enode->dump_dot (gv, args);
5164 /* Dump m_map, sorting it to avoid churn when comparing dumps. */
5165 auto_vec<function_call_string_cluster *> child_clusters (m_map.elements ());
5166 for (map_t::iterator iter = m_map.begin ();
5167 iter != m_map.end ();
5169 child_clusters.quick_push ((*iter).second);
5171 child_clusters.qsort (function_call_string_cluster::cmp_ptr_ptr);
5173 function_call_string_cluster *child_cluster;
5174 FOR_EACH_VEC_ELT (child_clusters, i, child_cluster)
5175 child_cluster->dump_dot (gv, args);
5178 void add_node (exploded_node *en) final override
5180 function *fun = en->get_function ();
5183 m_functionless_enodes.safe_push (en);
5187 const call_string &cs = en->get_point ().get_call_string ();
5188 function_call_string key (fun, &cs);
5189 function_call_string_cluster **slot = m_map.get (key);
5191 (*slot)->add_node (en);
5194 function_call_string_cluster *child
5195 = new function_call_string_cluster (fun, cs);
5196 m_map.put (key, child);
5197 child->add_node (en);
5202 typedef hash_map<function_call_string, function_call_string_cluster *> map_t;
5205 /* This should just be the origin exploded_node. */
5206 auto_vec <exploded_node *> m_functionless_enodes;
5209 /* Subclass of range_label for use within
5210 exploded_graph::dump_exploded_nodes for implementing
5211 -fdump-analyzer-exploded-nodes: a label for a specific
5214 class enode_label : public range_label
5217 enode_label (const extrinsic_state &ext_state,
5218 exploded_node *enode)
5219 : m_ext_state (ext_state), m_enode (enode) {}
5221 label_text get_text (unsigned) const final override
5224 pp_format_decoder (&pp) = default_tree_printer;
5225 m_enode->get_state ().dump_to_pp (m_ext_state, true, false, &pp);
5226 return make_label_text (false, "EN: %i: %s",
5227 m_enode->m_index, pp_formatted_text (&pp));
5231 const extrinsic_state &m_ext_state;
5232 exploded_node *m_enode;
5235 /* Postprocessing support for dumping the exploded nodes.
5236 Handle -fdump-analyzer-exploded-nodes,
5237 -fdump-analyzer-exploded-nodes-2, and the
5238 "__analyzer_dump_exploded_nodes" builtin. */
5241 exploded_graph::dump_exploded_nodes () const
5244 /* Locate calls to __analyzer_dump_exploded_nodes. */
5245 // Print how many egs there are for them?
5246 /* Better: log them as we go, and record the exploded nodes
5249 /* Show every enode. */
5251 /* Gather them by stmt, so that we can more clearly see the
5252 "hotspots" requiring numerous exploded nodes. */
5254 /* Alternatively, simply throw them all into one big rich_location
5255 and see if the label-printing will sort it out...
5256 This requires them all to be in the same source file. */
5258 if (flag_dump_analyzer_exploded_nodes)
5260 auto_timevar tv (TV_ANALYZER_DUMP);
5261 gcc_rich_location richloc (UNKNOWN_LOCATION);
5263 exploded_node *enode;
5264 FOR_EACH_VEC_ELT (m_nodes, i, enode)
5266 if (const gimple *stmt = enode->get_stmt ())
5268 if (get_pure_location (richloc.get_loc ()) == UNKNOWN_LOCATION)
5269 richloc.set_range (0, stmt->location, SHOW_RANGE_WITH_CARET);
5271 richloc.add_range (stmt->location,
5272 SHOW_RANGE_WITHOUT_CARET,
5273 new enode_label (m_ext_state, enode));
5276 warning_at (&richloc, 0, "%i exploded nodes", m_nodes.length ());
5278 /* Repeat the warning without all the labels, so that message is visible
5279 (the other one may well have scrolled past the terminal limit). */
5280 warning_at (richloc.get_loc (), 0,
5281 "%i exploded nodes", m_nodes.length ());
5283 if (m_worklist.length () > 0)
5284 warning_at (richloc.get_loc (), 0,
5285 "worklist still contains %i nodes", m_worklist.length ());
5288 /* Dump the egraph in textual form to a dump file. */
5289 if (flag_dump_analyzer_exploded_nodes_2)
5291 auto_timevar tv (TV_ANALYZER_DUMP);
5293 = concat (dump_base_name, ".eg.txt", NULL);
5294 FILE *outf = fopen (filename, "w");
5296 error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
5299 fprintf (outf, "exploded graph for %s\n", dump_base_name);
5300 fprintf (outf, " nodes: %i\n", m_nodes.length ());
5301 fprintf (outf, " edges: %i\n", m_edges.length ());
5304 exploded_node *enode;
5305 FOR_EACH_VEC_ELT (m_nodes, i, enode)
5307 fprintf (outf, "\nEN %i:\n", enode->m_index);
5308 enode->dump_succs_and_preds (outf);
5310 enode->get_point ().print (&pp, format (true));
5311 fprintf (outf, "%s\n", pp_formatted_text (&pp));
5312 enode->get_state ().dump_to_file (m_ext_state, false, true, outf);
5318 /* Dump the egraph in textual form to multiple dump files, one per enode. */
5319 if (flag_dump_analyzer_exploded_nodes_3)
5321 auto_timevar tv (TV_ANALYZER_DUMP);
5324 exploded_node *enode;
5325 FOR_EACH_VEC_ELT (m_nodes, i, enode)
5328 = xasprintf ("%s.en-%i.txt", dump_base_name, i);
5329 FILE *outf = fopen (filename, "w");
5331 error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
5334 fprintf (outf, "EN %i:\n", enode->m_index);
5335 enode->dump_succs_and_preds (outf);
5337 enode->get_point ().print (&pp, format (true));
5338 fprintf (outf, "%s\n", pp_formatted_text (&pp));
5339 enode->get_state ().dump_to_file (m_ext_state, false, true, outf);
5345 /* Emit a warning at any call to "__analyzer_dump_exploded_nodes",
5346 giving the number of processed exploded nodes for "before-stmt",
5347 and the IDs of processed, merger, and worklist enodes.
5349 We highlight the count of *processed* enodes since this is of most
5350 interest in DejaGnu tests for ensuring that state merger has
5353 We don't show the count of merger and worklist enodes, as this is
5354 more of an implementation detail of the merging/worklist that we
5355 don't want to bake into our expected DejaGnu messages. */
5358 exploded_node *enode;
5359 hash_set<const gimple *> seen;
5360 FOR_EACH_VEC_ELT (m_nodes, i, enode)
5362 if (enode->get_point ().get_kind () != PK_BEFORE_STMT)
5365 if (const gimple *stmt = enode->get_stmt ())
5366 if (const gcall *call = dyn_cast <const gcall *> (stmt))
5367 if (is_special_named_call_p (call, "__analyzer_dump_exploded_nodes",
5370 if (seen.contains (stmt))
5373 auto_vec<exploded_node *> processed_enodes;
5374 auto_vec<exploded_node *> merger_enodes;
5375 auto_vec<exploded_node *> worklist_enodes;
5376 /* This is O(N^2). */
5378 exploded_node *other_enode;
5379 FOR_EACH_VEC_ELT (m_nodes, j, other_enode)
5381 if (other_enode->get_point ().get_kind () != PK_BEFORE_STMT)
5383 if (other_enode->get_stmt () == stmt)
5384 switch (other_enode->get_status ())
5388 case exploded_node::STATUS_WORKLIST:
5389 worklist_enodes.safe_push (other_enode);
5391 case exploded_node::STATUS_PROCESSED:
5392 processed_enodes.safe_push (other_enode);
5394 case exploded_node::STATUS_MERGER:
5395 merger_enodes.safe_push (other_enode);
5401 pp_character (&pp, '[');
5402 print_enode_indices (&pp, processed_enodes);
5403 if (merger_enodes.length () > 0)
5405 pp_string (&pp, "] merger(s): [");
5406 print_enode_indices (&pp, merger_enodes);
5408 if (worklist_enodes.length () > 0)
5410 pp_string (&pp, "] worklist: [");
5411 print_enode_indices (&pp, worklist_enodes);
5413 pp_character (&pp, ']');
5415 warning_n (stmt->location, 0, processed_enodes.length (),
5416 "%i processed enode: %s",
5417 "%i processed enodes: %s",
5418 processed_enodes.length (), pp_formatted_text (&pp));
5421 /* If the argument is non-zero, then print all of the states
5422 of the various enodes. */
5423 tree t_arg = fold (gimple_call_arg (call, 0));
5424 if (TREE_CODE (t_arg) != INTEGER_CST)
5426 error_at (call->location,
5427 "integer constant required for arg 1");
5430 int i_arg = TREE_INT_CST_LOW (t_arg);
5433 exploded_node *other_enode;
5434 FOR_EACH_VEC_ELT (processed_enodes, j, other_enode)
5436 fprintf (stderr, "%i of %i: EN %i:\n",
5437 j + 1, processed_enodes.length (),
5438 other_enode->m_index);
5439 other_enode->dump_succs_and_preds (stderr);
5441 other_enode->get_state ().dump (m_ext_state, false);
5448 DEBUG_FUNCTION exploded_node *
5449 exploded_graph::get_node_by_index (int idx) const
5451 exploded_node *enode = m_nodes[idx];
5452 gcc_assert (enode->m_index == idx);
5456 /* Ensure that there is an exploded_node for a top-level call to FNDECL. */
5459 exploded_graph::on_escaped_function (tree fndecl)
5461 logger * const logger = get_logger ();
5462 LOG_FUNC_1 (logger, "%qE", fndecl);
5464 cgraph_node *cgnode = cgraph_node::get (fndecl);
5468 function *fun = cgnode->get_fun ();
5472 if (!gimple_has_body_p (fndecl))
5475 exploded_node *enode = add_function_entry (fun);
5479 logger->log ("created EN %i for %qE entrypoint",
5480 enode->m_index, fun->decl);
5482 logger->log ("did not create enode for %qE entrypoint", fun->decl);
5486 /* A collection of classes for visualizing the callgraph in .dot form
5487 (as represented in the supergraph). */
5489 /* Forward decls. */
5490 class viz_callgraph_node;
5491 class viz_callgraph_edge;
5492 class viz_callgraph;
5493 class viz_callgraph_cluster;
5495 /* Traits for using "digraph.h" to visualize the callgraph. */
5497 struct viz_callgraph_traits
5499 typedef viz_callgraph_node node_t;
5500 typedef viz_callgraph_edge edge_t;
5501 typedef viz_callgraph graph_t;
5504 dump_args_t (const exploded_graph *eg) : m_eg (eg) {}
5505 const exploded_graph *m_eg;
5507 typedef viz_callgraph_cluster cluster_t;
5510 /* Subclass of dnode representing a function within the callgraph. */
5512 class viz_callgraph_node : public dnode<viz_callgraph_traits>
5514 friend class viz_callgraph;
5517 viz_callgraph_node (function *fun, int index)
5518 : m_fun (fun), m_index (index), m_num_supernodes (0), m_num_superedges (0)
5523 void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
5525 pretty_printer *pp = gv->get_pp ();
5528 pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
5530 pp_write_text_to_stream (pp);
5532 pp_printf (pp, "VCG: %i: %s", m_index, function_name (m_fun));
5535 pp_printf (pp, "supernodes: %i\n", m_num_supernodes);
5538 pp_printf (pp, "superedges: %i\n", m_num_superedges);
5544 exploded_node *enode;
5545 unsigned num_enodes = 0;
5546 FOR_EACH_VEC_ELT (args.m_eg->m_nodes, i, enode)
5548 if (enode->get_point ().get_function () == m_fun)
5551 pp_printf (pp, "enodes: %i\n", num_enodes);
5554 // TODO: also show the per-callstring breakdown
5555 const exploded_graph::call_string_data_map_t *per_cs_data
5556 = args.m_eg->get_per_call_string_data ();
5557 for (exploded_graph::call_string_data_map_t::iterator iter
5558 = per_cs_data->begin ();
5559 iter != per_cs_data->end ();
5562 const call_string *cs = (*iter).first;
5563 //per_call_string_data *data = (*iter).second;
5565 FOR_EACH_VEC_ELT (args.m_eg->m_nodes, i, enode)
5567 if (enode->get_point ().get_function () == m_fun
5568 && &enode->get_point ().get_call_string () == cs)
5574 pp_printf (pp, ": %i\n", num_enodes);
5578 /* Show any summaries. */
5579 per_function_data *data = args.m_eg->get_per_function_data (m_fun);
5583 pp_printf (pp, "summaries: %i\n", data->m_summaries.length ());
5584 for (auto summary : data->m_summaries)
5586 pp_printf (pp, "\nsummary: %s:\n", summary->get_desc ().get ());
5587 const extrinsic_state &ext_state = args.m_eg->get_ext_state ();
5588 const program_state &state = summary->get_state ();
5589 state.dump_to_pp (ext_state, false, true, pp);
5595 pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
5596 pp_string (pp, "\"];\n\n");
5600 void dump_dot_id (pretty_printer *pp) const
5602 pp_printf (pp, "vcg_%i", m_index);
5608 int m_num_supernodes;
5609 int m_num_superedges;
5612 /* Subclass of dedge representing a callgraph edge. */
5614 class viz_callgraph_edge : public dedge<viz_callgraph_traits>
5617 viz_callgraph_edge (viz_callgraph_node *src, viz_callgraph_node *dest)
5618 : dedge<viz_callgraph_traits> (src, dest)
5621 void dump_dot (graphviz_out *gv, const dump_args_t &) const
5624 pretty_printer *pp = gv->get_pp ();
5626 const char *style = "\"solid,bold\"";
5627 const char *color = "black";
5629 const char *constraint = "true";
5631 m_src->dump_dot_id (pp);
5632 pp_string (pp, " -> ");
5633 m_dest->dump_dot_id (pp);
5635 (" [style=%s, color=%s, weight=%d, constraint=%s,"
5637 style, color, weight, constraint);
5638 pp_printf (pp, "\"];\n");
5642 /* Subclass of digraph representing the callgraph. */
5644 class viz_callgraph : public digraph<viz_callgraph_traits>
5647 viz_callgraph (const supergraph &sg);
5649 viz_callgraph_node *get_vcg_node_for_function (function *fun)
5651 return *m_map.get (fun);
5654 viz_callgraph_node *get_vcg_node_for_snode (supernode *snode)
5656 return get_vcg_node_for_function (snode->m_fun);
5660 hash_map<function *, viz_callgraph_node *> m_map;
5663 /* Placeholder subclass of cluster. */
5665 class viz_callgraph_cluster : public cluster<viz_callgraph_traits>
5669 /* viz_callgraph's ctor. */
5671 viz_callgraph::viz_callgraph (const supergraph &sg)
5674 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
5676 function *fun = node->get_fun ();
5677 viz_callgraph_node *vcg_node
5678 = new viz_callgraph_node (fun, m_nodes.length ());
5679 m_map.put (fun, vcg_node);
5680 add_node (vcg_node);
5685 FOR_EACH_VEC_ELT (sg.m_edges, i, sedge)
5687 viz_callgraph_node *vcg_src = get_vcg_node_for_snode (sedge->m_src);
5689 get_vcg_node_for_function (vcg_src->m_fun)->m_num_superedges++;
5690 if (sedge->dyn_cast_call_superedge ())
5692 viz_callgraph_node *vcg_dest = get_vcg_node_for_snode (sedge->m_dest);
5693 viz_callgraph_edge *vcg_edge
5694 = new viz_callgraph_edge (vcg_src, vcg_dest);
5695 add_edge (vcg_edge);
5700 FOR_EACH_VEC_ELT (sg.m_nodes, i, snode)
5703 get_vcg_node_for_function (snode->m_fun)->m_num_supernodes++;
5707 /* Dump the callgraph to FILENAME. */
5710 dump_callgraph (const supergraph &sg, const char *filename,
5711 const exploded_graph *eg)
5713 FILE *outf = fopen (filename, "w");
5718 viz_callgraph vcg (sg);
5719 vcg.dump_dot (filename, NULL, viz_callgraph_traits::dump_args_t (eg));
5724 /* Dump the callgraph to "<srcfile>.callgraph.dot". */
5727 dump_callgraph (const supergraph &sg, const exploded_graph *eg)
5729 auto_timevar tv (TV_ANALYZER_DUMP);
5730 char *filename = concat (dump_base_name, ".callgraph.dot", NULL);
5731 dump_callgraph (sg, filename, eg);
5735 /* Subclass of dot_annotator for implementing
5736 DUMP_BASE_NAME.supergraph-eg.dot, a post-analysis dump of the supergraph.
5738 Annotate the supergraph nodes by printing the exploded nodes in concise
5739 form within them, next to their pertinent statements where appropriate,
5740 colorizing the exploded nodes based on sm-state.
5741 Also show saved diagnostics within the exploded nodes, giving information
5742 on whether they were feasible, and, if infeasible, where the problem
5745 class exploded_graph_annotator : public dot_annotator
5748 exploded_graph_annotator (const exploded_graph &eg)
5751 /* Avoid O(N^2) by prepopulating m_enodes_per_snodes. */
5754 FOR_EACH_VEC_ELT (eg.get_supergraph ().m_nodes, i, snode)
5755 m_enodes_per_snodes.safe_push (new auto_vec <exploded_node *> ());
5756 exploded_node *enode;
5757 FOR_EACH_VEC_ELT (m_eg.m_nodes, i, enode)
5758 if (enode->get_supernode ())
5759 m_enodes_per_snodes[enode->get_supernode ()->m_index]->safe_push (enode);
5762 /* Show exploded nodes for BEFORE_SUPERNODE points before N. */
5763 bool add_node_annotations (graphviz_out *gv, const supernode &n,
5765 const final override
5770 pretty_printer *pp = gv->get_pp ();
5773 pp_string (pp, "BEFORE");
5774 pp_printf (pp, " (scc: %i)", m_eg.get_scc_id (n));
5778 exploded_node *enode;
5779 bool had_enode = false;
5780 FOR_EACH_VEC_ELT (*m_enodes_per_snodes[n.m_index], i, enode)
5782 gcc_assert (enode->get_supernode () == &n);
5783 const program_point &point = enode->get_point ();
5784 if (point.get_kind () != PK_BEFORE_SUPERNODE)
5786 print_enode (gv, enode);
5790 pp_string (pp, "<TD BGCOLOR=\"red\">UNREACHED</TD>");
5796 /* Show exploded nodes for STMT. */
5797 void add_stmt_annotations (graphviz_out *gv, const gimple *stmt,
5799 const final override
5803 pretty_printer *pp = gv->get_pp ();
5805 const supernode *snode
5806 = m_eg.get_supergraph ().get_supernode_for_stmt (stmt);
5808 exploded_node *enode;
5809 bool had_td = false;
5810 FOR_EACH_VEC_ELT (*m_enodes_per_snodes[snode->m_index], i, enode)
5812 const program_point &point = enode->get_point ();
5813 if (point.get_kind () != PK_BEFORE_STMT)
5815 if (point.get_stmt () != stmt)
5817 print_enode (gv, enode);
5828 /* Show exploded nodes for AFTER_SUPERNODE points after N. */
5829 bool add_after_node_annotations (graphviz_out *gv, const supernode &n)
5830 const final override
5833 pretty_printer *pp = gv->get_pp ();
5836 pp_string (pp, "AFTER");
5840 exploded_node *enode;
5841 FOR_EACH_VEC_ELT (*m_enodes_per_snodes[n.m_index], i, enode)
5843 gcc_assert (enode->get_supernode () == &n);
5844 const program_point &point = enode->get_point ();
5845 if (point.get_kind () != PK_AFTER_SUPERNODE)
5847 print_enode (gv, enode);
5855 /* Concisely print a TD element for ENODE, showing the index, status,
5856 and any saved_diagnostics at the enode. Colorize it to show sm-state.
5858 Ideally we'd dump ENODE's state here, hidden behind some kind of
5859 interactive disclosure method like a tooltip, so that the states
5860 can be explored without overwhelming the graph.
5861 However, I wasn't able to get graphviz/xdot to show tooltips on
5862 individual elements within a HTML-like label. */
5863 void print_enode (graphviz_out *gv, const exploded_node *enode) const
5865 pretty_printer *pp = gv->get_pp ();
5866 pp_printf (pp, "<TD BGCOLOR=\"%s\">",
5867 enode->get_dot_fillcolor ());
5868 pp_printf (pp, "<TABLE BORDER=\"0\">");
5870 pp_printf (pp, "EN: %i", enode->m_index);
5871 switch (enode->get_status ())
5875 case exploded_node::STATUS_WORKLIST:
5876 pp_string (pp, "(W)");
5878 case exploded_node::STATUS_PROCESSED:
5880 case exploded_node::STATUS_MERGER:
5881 pp_string (pp, "(M)");
5883 case exploded_node::STATUS_BULK_MERGED:
5884 pp_string (pp, "(BM)");
5889 /* Dump any saved_diagnostics at this enode. */
5890 for (unsigned i = 0; i < enode->get_num_diagnostics (); i++)
5892 const saved_diagnostic *sd = enode->get_saved_diagnostic (i);
5893 print_saved_diagnostic (gv, sd);
5895 pp_printf (pp, "</TABLE>");
5896 pp_printf (pp, "</TD>");
5899 /* Print a TABLE element for SD, showing the kind, the length of the
5900 exploded_path, whether the path was feasible, and if infeasible,
5901 what the problem was. */
5902 void print_saved_diagnostic (graphviz_out *gv,
5903 const saved_diagnostic *sd) const
5905 pretty_printer *pp = gv->get_pp ();
5907 pp_printf (pp, "<TABLE BORDER=\"0\">");
5909 pp_string (pp, "<TD BGCOLOR=\"green\">");
5910 pp_printf (pp, "DIAGNOSTIC: %s", sd->m_d->get_kind ());
5913 if (sd->get_best_epath ())
5914 pp_printf (pp, "epath length: %i", sd->get_epath_length ());
5916 pp_printf (pp, "no best epath");
5918 if (const feasibility_problem *p = sd->get_feasibility_problem ())
5921 pp_printf (pp, "INFEASIBLE at eedge %i: EN:%i -> EN:%i",
5923 p->m_eedge.m_src->m_index,
5924 p->m_eedge.m_dest->m_index);
5925 pp_write_text_as_html_like_dot_to_stream (pp);
5928 p->m_eedge.m_sedge->dump (pp);
5929 pp_write_text_as_html_like_dot_to_stream (pp);
5932 pp_gimple_stmt_1 (pp, p->m_last_stmt, 0, (dump_flags_t)0);
5933 pp_write_text_as_html_like_dot_to_stream (pp);
5935 /* Ideally we'd print p->m_model here; see the notes above about
5938 pp_printf (pp, "</TABLE>");
5942 const exploded_graph &m_eg;
5943 auto_delete_vec<auto_vec <exploded_node *> > m_enodes_per_snodes;
5946 /* Implement -fdump-analyzer-json. */
5949 dump_analyzer_json (const supergraph &sg,
5950 const exploded_graph &eg)
5952 auto_timevar tv (TV_ANALYZER_DUMP);
5953 char *filename = concat (dump_base_name, ".analyzer.json.gz", NULL);
5954 gzFile output = gzopen (filename, "w");
5957 error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
5962 json::object *toplev_obj = new json::object ();
5963 toplev_obj->set ("sgraph", sg.to_json ());
5964 toplev_obj->set ("egraph", eg.to_json ());
5967 toplev_obj->print (&pp);
5968 pp_formatted_text (&pp);
5972 if (gzputs (output, pp_formatted_text (&pp)) == EOF
5973 || gzclose (output))
5974 error_at (UNKNOWN_LOCATION, "error writing %qs", filename);
5979 /* Concrete subclass of plugin_analyzer_init_iface, allowing plugins
5980 to register new state machines. */
5982 class plugin_analyzer_init_impl : public plugin_analyzer_init_iface
5985 plugin_analyzer_init_impl (auto_delete_vec <state_machine> *checkers,
5986 known_function_manager *known_fn_mgr,
5988 : m_checkers (checkers),
5989 m_known_fn_mgr (known_fn_mgr),
5993 void register_state_machine (std::unique_ptr<state_machine> sm) final override
5995 LOG_SCOPE (m_logger);
5996 m_checkers->safe_push (sm.release ());
5999 void register_known_function (const char *name,
6000 std::unique_ptr<known_function> kf) final override
6002 LOG_SCOPE (m_logger);
6003 m_known_fn_mgr->add (name, std::move (kf));
6006 logger *get_logger () const final override
6012 auto_delete_vec <state_machine> *m_checkers;
6013 known_function_manager *m_known_fn_mgr;
6017 /* Run the analysis "engine". */
6020 impl_run_checkers (logger *logger)
6026 logger->log ("BITS_BIG_ENDIAN: %i", BITS_BIG_ENDIAN ? 1 : 0);
6027 logger->log ("BYTES_BIG_ENDIAN: %i", BYTES_BIG_ENDIAN ? 1 : 0);
6028 logger->log ("WORDS_BIG_ENDIAN: %i", WORDS_BIG_ENDIAN ? 1 : 0);
6029 log_stashed_constants (logger);
6032 /* If using LTO, ensure that the cgraph nodes have function bodies. */
6034 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
6035 node->get_untransformed_body ();
6037 /* Create the supergraph. */
6038 supergraph sg (logger);
6040 engine eng (&sg, logger);
6042 state_purge_map *purge_map = NULL;
6044 if (flag_analyzer_state_purge)
6045 purge_map = new state_purge_map (sg, eng.get_model_manager (), logger);
6047 if (flag_dump_analyzer_supergraph)
6049 /* Dump supergraph pre-analysis. */
6050 auto_timevar tv (TV_ANALYZER_DUMP);
6051 char *filename = concat (dump_base_name, ".supergraph.dot", NULL);
6052 supergraph::dump_args_t args ((enum supergraph_dot_flags)0, NULL);
6053 sg.dump_dot (filename, args);
6057 if (flag_dump_analyzer_state_purge)
6059 auto_timevar tv (TV_ANALYZER_DUMP);
6060 state_purge_annotator a (purge_map);
6061 char *filename = concat (dump_base_name, ".state-purge.dot", NULL);
6062 supergraph::dump_args_t args ((enum supergraph_dot_flags)0, &a);
6063 sg.dump_dot (filename, args);
6067 auto_delete_vec <state_machine> checkers;
6068 make_checkers (checkers, logger);
6070 register_known_functions (*eng.get_known_function_manager ());
6072 plugin_analyzer_init_impl data (&checkers,
6073 eng.get_known_function_manager (),
6075 invoke_plugin_callbacks (PLUGIN_ANALYZER_INIT, &data);
6081 FOR_EACH_VEC_ELT (checkers, i, sm)
6082 logger->log ("checkers[%i]: %s", i, sm->get_name ());
6085 /* Extrinsic state shared by nodes in the graph. */
6086 const extrinsic_state ext_state (checkers, &eng, logger);
6088 const analysis_plan plan (sg, logger);
6090 /* The exploded graph. */
6091 exploded_graph eg (sg, logger, ext_state, purge_map, plan,
6092 analyzer_verbosity);
6094 /* Add entrypoints to the graph for externally-callable functions. */
6095 eg.build_initial_worklist ();
6097 /* Now process the worklist, exploring the <point, state> graph. */
6098 eg.process_worklist ();
6100 if (flag_dump_analyzer_exploded_graph)
6102 auto_timevar tv (TV_ANALYZER_DUMP);
6104 = concat (dump_base_name, ".eg.dot", NULL);
6105 exploded_graph::dump_args_t args (eg);
6107 eg.dump_dot (filename, &c, args);
6111 /* Now emit any saved diagnostics. */
6112 eg.get_diagnostic_manager ().emit_saved_diagnostics (eg);
6114 eg.dump_exploded_nodes ();
6118 if (flag_dump_analyzer_callgraph)
6119 dump_callgraph (sg, &eg);
6121 if (flag_dump_analyzer_supergraph)
6123 /* Dump post-analysis form of supergraph. */
6124 auto_timevar tv (TV_ANALYZER_DUMP);
6125 char *filename = concat (dump_base_name, ".supergraph-eg.dot", NULL);
6126 exploded_graph_annotator a (eg);
6127 supergraph::dump_args_t args ((enum supergraph_dot_flags)0, &a);
6128 sg.dump_dot (filename, args);
6132 if (flag_dump_analyzer_json)
6133 dump_analyzer_json (sg, eg);
6135 if (flag_dump_analyzer_untracked)
6136 eng.get_model_manager ()->dump_untracked_regions ();
6141 /* Handle -fdump-analyzer and -fdump-analyzer-stderr. */
6142 static FILE *dump_fout = NULL;
6144 /* Track if we're responsible for closing dump_fout. */
6145 static bool owns_dump_fout = false;
6147 /* If dumping is enabled, attempt to create dump_fout if it hasn't already
6148 been opened. Return it. */
6151 get_or_create_any_logfile ()
6155 if (flag_dump_analyzer_stderr)
6157 else if (flag_dump_analyzer)
6159 char *dump_filename = concat (dump_base_name, ".analyzer.txt", NULL);
6160 dump_fout = fopen (dump_filename, "w");
6161 free (dump_filename);
6163 owns_dump_fout = true;
6169 /* External entrypoint to the analysis "engine".
6170 Set up any dumps, then call impl_run_checkers. */
6175 /* Save input_location. */
6176 location_t saved_input_location = input_location;
6179 log_user the_logger (NULL);
6180 get_or_create_any_logfile ();
6182 the_logger.set_logger (new logger (dump_fout, 0, 0,
6183 *global_dc->printer));
6184 LOG_SCOPE (the_logger.get_logger ());
6186 impl_run_checkers (the_logger.get_logger ());
6188 /* end of lifetime of the_logger (so that dump file is closed after the
6189 various dtors run). */
6195 owns_dump_fout = false;
6199 /* Restore input_location. Subsequent passes may assume that input_location
6200 is some arbitrary value *not* in the block tree, which might be violated
6201 if we didn't restore it. */
6202 input_location = saved_input_location;
6207 #endif /* #if ENABLE_ANALYZER */