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 (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,
2049 ? m_dynamic_call->location
2050 : UNKNOWN_LOCATION),
2051 dest_point.get_fndecl (),
2054 emission_path->add_event
2055 (make_unique<call_event> (eedge,
2057 ? m_dynamic_call->location
2058 : UNKNOWN_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>
2106 (&eedge, get_longjmp_call ()->location,
2107 src_point.get_fndecl (),
2108 src_stack_depth, this));
2109 emission_path->add_event
2110 (make_unique<rewind_to_setjmp_event>
2111 (&eedge, get_setjmp_call ()->location,
2112 dst_point.get_fndecl (),
2113 dst_stack_depth, this));
2116 /* class exploded_edge : public dedge<eg_traits>. */
2118 /* exploded_edge's ctor. */
2120 exploded_edge::exploded_edge (exploded_node *src, exploded_node *dest,
2121 const superedge *sedge,
2122 std::unique_ptr<custom_edge_info> custom_info)
2123 : dedge<eg_traits> (src, dest), m_sedge (sedge),
2124 m_custom_info (std::move (custom_info))
2128 /* Implementation of dedge::dump_dot vfunc for exploded_edge.
2129 Use the label of the underlying superedge, if any. */
2132 exploded_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const
2134 pretty_printer *pp = gv->get_pp ();
2136 m_src->dump_dot_id (pp);
2137 pp_string (pp, " -> ");
2138 m_dest->dump_dot_id (pp);
2139 dump_dot_label (pp);
2142 /* Second half of exploded_edge::dump_dot. This is split out
2143 for use by trimmed_graph::dump_dot and base_feasible_edge::dump_dot. */
2146 exploded_edge::dump_dot_label (pretty_printer *pp) const
2148 const char *style = "\"solid,bold\"";
2149 const char *color = "black";
2151 const char *constraint = "true";
2154 switch (m_sedge->m_kind)
2158 case SUPEREDGE_CFG_EDGE:
2160 case SUPEREDGE_CALL:
2162 //constraint = "false";
2164 case SUPEREDGE_RETURN:
2166 //constraint = "false";
2168 case SUPEREDGE_INTRAPROCEDURAL_CALL:
2169 style = "\"dotted\"";
2175 style = "\"dotted\"";
2179 (" [style=%s, color=%s, weight=%d, constraint=%s,"
2181 style, color, weight, constraint);
2184 m_sedge->dump_label_to_pp (pp, false);
2185 else if (m_custom_info)
2186 m_custom_info->print (pp);
2188 //pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
2190 pp_printf (pp, "\"];\n");
2193 /* Return a new json::object of the form
2194 {"src_idx": int, the index of the source exploded edge,
2195 "dst_idx": int, the index of the destination exploded edge,
2196 "sedge": (optional) object for the superedge, if any,
2197 "custom": (optional) str, a description, if this is a custom edge}. */
2200 exploded_edge::to_json () const
2202 json::object *eedge_obj = new json::object ();
2203 eedge_obj->set ("src_idx", new json::integer_number (m_src->m_index));
2204 eedge_obj->set ("dst_idx", new json::integer_number (m_dest->m_index));
2206 eedge_obj->set ("sedge", m_sedge->to_json ());
2210 pp_format_decoder (&pp) = default_tree_printer;
2211 m_custom_info->print (&pp);
2212 eedge_obj->set ("custom", new json::string (pp_formatted_text (&pp)));
2221 stats::stats (int num_supernodes)
2222 : m_node_reuse_count (0),
2223 m_node_reuse_after_merge_count (0),
2224 m_num_supernodes (num_supernodes)
2226 for (int i = 0; i < NUM_POINT_KINDS; i++)
2230 /* Log these stats in multiline form to LOGGER. */
2233 stats::log (logger *logger) const
2235 gcc_assert (logger);
2236 for (int i = 0; i < NUM_POINT_KINDS; i++)
2237 if (m_num_nodes[i] > 0)
2238 logger->log ("m_num_nodes[%s]: %i",
2239 point_kind_to_string (static_cast <enum point_kind> (i)),
2241 logger->log ("m_node_reuse_count: %i", m_node_reuse_count);
2242 logger->log ("m_node_reuse_after_merge_count: %i",
2243 m_node_reuse_after_merge_count);
2246 /* Dump these stats in multiline form to OUT. */
2249 stats::dump (FILE *out) const
2251 for (int i = 0; i < NUM_POINT_KINDS; i++)
2252 if (m_num_nodes[i] > 0)
2253 fprintf (out, "m_num_nodes[%s]: %i\n",
2254 point_kind_to_string (static_cast <enum point_kind> (i)),
2256 fprintf (out, "m_node_reuse_count: %i\n", m_node_reuse_count);
2257 fprintf (out, "m_node_reuse_after_merge_count: %i\n",
2258 m_node_reuse_after_merge_count);
2260 if (m_num_supernodes > 0)
2261 fprintf (out, "PK_AFTER_SUPERNODE nodes per supernode: %.2f\n",
2262 (float)m_num_nodes[PK_AFTER_SUPERNODE] / (float)m_num_supernodes);
2265 /* Return the total number of enodes recorded within this object. */
2268 stats::get_total_enodes () const
2271 for (int i = 0; i < NUM_POINT_KINDS; i++)
2272 result += m_num_nodes[i];
2276 /* struct per_function_data. */
2278 per_function_data::~per_function_data ()
2280 for (auto iter : m_summaries)
2285 per_function_data::add_call_summary (exploded_node *node)
2287 m_summaries.safe_push (new call_summary (this, node));
2290 /* strongly_connected_components's ctor. Tarjan's SCC algorithm. */
2292 strongly_connected_components::
2293 strongly_connected_components (const supergraph &sg, logger *logger)
2294 : m_sg (sg), m_per_node (m_sg.num_nodes ())
2297 auto_timevar tv (TV_ANALYZER_SCC);
2299 for (int i = 0; i < m_sg.num_nodes (); i++)
2300 m_per_node.quick_push (per_node_data ());
2302 for (int i = 0; i < m_sg.num_nodes (); i++)
2303 if (m_per_node[i].m_index == -1)
2310 /* Dump this object to stderr. */
2313 strongly_connected_components::dump () const
2315 for (int i = 0; i < m_sg.num_nodes (); i++)
2317 const per_node_data &v = m_per_node[i];
2318 fprintf (stderr, "SN %i: index: %i lowlink: %i on_stack: %i\n",
2319 i, v.m_index, v.m_lowlink, v.m_on_stack);
2323 /* Return a new json::array of per-snode SCC ids. */
2326 strongly_connected_components::to_json () const
2328 json::array *scc_arr = new json::array ();
2329 for (int i = 0; i < m_sg.num_nodes (); i++)
2330 scc_arr->append (new json::integer_number (get_scc_id (i)));
2334 /* Subroutine of strongly_connected_components's ctor, part of Tarjan's
2338 strongly_connected_components::strong_connect (unsigned index)
2340 supernode *v_snode = m_sg.get_node_by_index (index);
2342 /* Set the depth index for v to the smallest unused index. */
2343 per_node_data *v = &m_per_node[index];
2345 v->m_lowlink = index;
2346 m_stack.safe_push (index);
2347 v->m_on_stack = true;
2350 /* Consider successors of v. */
2353 FOR_EACH_VEC_ELT (v_snode->m_succs, i, sedge)
2355 if (sedge->get_kind () != SUPEREDGE_CFG_EDGE
2356 && sedge->get_kind () != SUPEREDGE_INTRAPROCEDURAL_CALL)
2358 supernode *w_snode = sedge->m_dest;
2359 per_node_data *w = &m_per_node[w_snode->m_index];
2360 if (w->m_index == -1)
2362 /* Successor w has not yet been visited; recurse on it. */
2363 strong_connect (w_snode->m_index);
2364 v->m_lowlink = MIN (v->m_lowlink, w->m_lowlink);
2366 else if (w->m_on_stack)
2368 /* Successor w is in stack S and hence in the current SCC
2369 If w is not on stack, then (v, w) is a cross-edge in the DFS
2370 tree and must be ignored. */
2371 v->m_lowlink = MIN (v->m_lowlink, w->m_index);
2375 /* If v is a root node, pop the stack and generate an SCC. */
2377 if (v->m_lowlink == v->m_index)
2381 int idx = m_stack.pop ();
2382 w = &m_per_node[idx];
2383 w->m_on_stack = false;
2388 /* worklist's ctor. */
2390 worklist::worklist (const exploded_graph &eg, const analysis_plan &plan)
2391 : m_scc (eg.get_supergraph (), eg.get_logger ()),
2393 m_queue (key_t (*this, NULL))
2397 /* Return the number of nodes in the worklist. */
2400 worklist::length () const
2402 return m_queue.nodes ();
2405 /* Return the next node in the worklist, removing it. */
2408 worklist::take_next ()
2410 return m_queue.extract_min ();
2413 /* Return the next node in the worklist without removing it. */
2416 worklist::peek_next ()
2418 return m_queue.min ();
2421 /* Add ENODE to the worklist. */
2424 worklist::add_node (exploded_node *enode)
2426 gcc_assert (enode->get_status () == exploded_node::STATUS_WORKLIST);
2427 m_queue.insert (key_t (*this, enode), enode);
2430 /* Comparator for implementing worklist::key_t comparison operators.
2431 Return negative if KA is before KB
2432 Return positive if KA is after KB
2433 Return 0 if they are equal.
2435 The ordering of the worklist is critical for performance and for
2436 avoiding node explosions. Ideally we want all enodes at a CFG join-point
2437 with the same callstring to be sorted next to each other in the worklist
2438 so that a run of consecutive enodes can be merged and processed "in bulk"
2439 rather than individually or pairwise, minimizing the number of new enodes
2443 worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb)
2445 const program_point &point_a = ka.m_enode->get_point ();
2446 const program_point &point_b = kb.m_enode->get_point ();
2447 const call_string &call_string_a = point_a.get_call_string ();
2448 const call_string &call_string_b = point_b.get_call_string ();
2450 /* Order empty-callstring points with different functions based on the
2451 analysis_plan, so that we generate summaries before they are used. */
2452 if (flag_analyzer_call_summaries
2453 && call_string_a.empty_p ()
2454 && call_string_b.empty_p ()
2455 && point_a.get_function () != NULL
2456 && point_b.get_function () != NULL
2457 && point_a.get_function () != point_b.get_function ())
2459 if (int cmp = ka.m_worklist.m_plan.cmp_function (point_a.get_function (),
2460 point_b.get_function ()))
2464 /* Sort by callstring, so that nodes with deeper call strings are processed
2465 before those with shallower call strings.
2474 then we want the path inside the function call to be fully explored up
2475 to the return to the join BB before we explore on the "no fn call" path,
2476 so that both enodes at the join BB reach the front of the worklist at
2477 the same time and thus have a chance of being merged. */
2478 int cs_cmp = call_string::cmp (call_string_a, call_string_b);
2483 int scc_id_a = ka.get_scc_id (ka.m_enode);
2484 int scc_id_b = kb.get_scc_id (kb.m_enode);
2485 if (scc_id_a != scc_id_b)
2486 return scc_id_a - scc_id_b;
2488 /* If in same SCC, order by supernode index (an arbitrary but stable
2490 const supernode *snode_a = ka.m_enode->get_supernode ();
2491 const supernode *snode_b = kb.m_enode->get_supernode ();
2492 if (snode_a == NULL)
2494 if (snode_b != NULL)
2498 /* Both are NULL. */
2501 if (snode_b == NULL)
2504 /* Neither are NULL. */
2505 gcc_assert (snode_a && snode_b);
2506 if (snode_a->m_index != snode_b->m_index)
2507 return snode_a->m_index - snode_b->m_index;
2509 gcc_assert (snode_a == snode_b);
2511 /* Order within supernode via program point. */
2512 int within_snode_cmp
2513 = function_point::cmp_within_supernode (point_a.get_function_point (),
2514 point_b.get_function_point ());
2515 if (within_snode_cmp)
2516 return within_snode_cmp;
2518 /* Otherwise, we ought to have the same program_point. */
2519 gcc_assert (point_a == point_b);
2521 const program_state &state_a = ka.m_enode->get_state ();
2522 const program_state &state_b = kb.m_enode->get_state ();
2524 /* Sort by sm-state, so that identical sm-states are grouped
2525 together in the worklist. */
2526 for (unsigned sm_idx = 0; sm_idx < state_a.m_checker_states.length ();
2529 sm_state_map *smap_a = state_a.m_checker_states[sm_idx];
2530 sm_state_map *smap_b = state_b.m_checker_states[sm_idx];
2532 if (int smap_cmp = sm_state_map::cmp (*smap_a, *smap_b))
2536 /* Otherwise, we have two enodes at the same program point but with
2537 different states. We don't have a good total ordering on states,
2538 so order them by enode index, so that we have at least have a
2540 return ka.m_enode->m_index - kb.m_enode->m_index;
2543 /* Return a new json::object of the form
2544 {"scc" : [per-snode-IDs]}, */
2547 worklist::to_json () const
2549 json::object *worklist_obj = new json::object ();
2551 worklist_obj->set ("scc", m_scc.to_json ());
2553 /* The following field isn't yet being JSONified:
2556 return worklist_obj;
2559 /* exploded_graph's ctor. */
2561 exploded_graph::exploded_graph (const supergraph &sg, logger *logger,
2562 const extrinsic_state &ext_state,
2563 const state_purge_map *purge_map,
2564 const analysis_plan &plan,
2566 : m_sg (sg), m_logger (logger),
2567 m_worklist (*this, plan),
2568 m_ext_state (ext_state),
2569 m_purge_map (purge_map),
2571 m_diagnostic_manager (logger, ext_state.get_engine (), verbosity),
2572 m_global_stats (m_sg.num_nodes ()),
2573 m_functionless_stats (m_sg.num_nodes ()),
2574 m_PK_AFTER_SUPERNODE_per_snode (m_sg.num_nodes ())
2576 m_origin = get_or_create_node
2577 (program_point::origin (*ext_state.get_model_manager ()),
2578 program_state (ext_state), NULL);
2579 for (int i = 0; i < m_sg.num_nodes (); i++)
2580 m_PK_AFTER_SUPERNODE_per_snode.quick_push (i);
2583 /* exploded_graph's dtor. */
2585 exploded_graph::~exploded_graph ()
2587 for (auto iter : m_per_point_data)
2589 for (auto iter : m_per_function_data)
2591 for (auto iter : m_per_function_stats)
2593 for (auto iter : m_per_call_string_data)
2597 /* Subroutine for use when implementing __attribute__((tainted_args))
2598 on functions and on function pointer fields in structs.
2600 Called on STATE representing a call to FNDECL.
2601 Mark all params of FNDECL in STATE as "tainted". Mark the value of all
2602 regions pointed to by params of FNDECL as "tainted".
2604 Return true if successful; return false if the "taint" state machine
2608 mark_params_as_tainted (program_state *state, tree fndecl,
2609 const extrinsic_state &ext_state)
2611 unsigned taint_sm_idx;
2612 if (!ext_state.get_sm_idx_by_name ("taint", &taint_sm_idx))
2614 sm_state_map *smap = state->m_checker_states[taint_sm_idx];
2616 const state_machine &sm = ext_state.get_sm (taint_sm_idx);
2617 state_machine::state_t tainted = sm.get_state_by_name ("tainted");
2619 region_model_manager *mgr = ext_state.get_model_manager ();
2621 function *fun = DECL_STRUCT_FUNCTION (fndecl);
2624 for (tree iter_parm = DECL_ARGUMENTS (fndecl); iter_parm;
2625 iter_parm = DECL_CHAIN (iter_parm))
2627 tree param = iter_parm;
2628 if (tree parm_default_ssa = ssa_default_def (fun, iter_parm))
2629 param = parm_default_ssa;
2630 const region *param_reg = state->m_region_model->get_lvalue (param, NULL);
2631 const svalue *init_sval = mgr->get_or_create_initial_value (param_reg);
2632 smap->set_state (state->m_region_model, init_sval,
2633 tainted, NULL /*origin_new_sval*/, ext_state);
2634 if (POINTER_TYPE_P (TREE_TYPE (param)))
2636 const region *pointee_reg = mgr->get_symbolic_region (init_sval);
2637 /* Mark "*param" as tainted. */
2638 const svalue *init_pointee_sval
2639 = mgr->get_or_create_initial_value (pointee_reg);
2640 smap->set_state (state->m_region_model, init_pointee_sval,
2641 tainted, NULL /*origin_new_sval*/, ext_state);
2648 /* Custom event for use by tainted_args_function_info when a function
2649 has been marked with __attribute__((tainted_args)). */
2651 class tainted_args_function_custom_event : public custom_event
2654 tainted_args_function_custom_event (location_t loc, tree fndecl, int depth)
2655 : custom_event (loc, fndecl, depth),
2660 label_text get_desc (bool can_colorize) const final override
2662 return make_label_text
2664 "function %qE marked with %<__attribute__((tainted_args))%>",
2672 /* Custom exploded_edge info for top-level calls to a function
2673 marked with __attribute__((tainted_args)). */
2675 class tainted_args_function_info : public custom_edge_info
2678 tainted_args_function_info (tree fndecl)
2682 void print (pretty_printer *pp) const final override
2684 pp_string (pp, "call to tainted_args function");
2687 bool update_model (region_model *,
2688 const exploded_edge *,
2689 region_model_context *) const final override
2695 void add_events_to_path (checker_path *emission_path,
2696 const exploded_edge &) const final override
2698 emission_path->add_event
2699 (make_unique<tainted_args_function_custom_event>
2700 (DECL_SOURCE_LOCATION (m_fndecl), m_fndecl, 0));
2707 /* Ensure that there is an exploded_node representing an external call to
2708 FUN, adding it to the worklist if creating it.
2710 Add an edge from the origin exploded_node to the function entrypoint
2713 Return the exploded_node for the entrypoint to the function. */
2716 exploded_graph::add_function_entry (function *fun)
2718 gcc_assert (gimple_has_body_p (fun->decl));
2720 /* Be idempotent. */
2721 if (m_functions_with_enodes.contains (fun))
2723 logger * const logger = get_logger ();
2725 logger->log ("entrypoint for %qE already exists", fun->decl);
2730 = program_point::from_function_entry (*m_ext_state.get_model_manager (),
2732 program_state state (m_ext_state);
2733 state.push_frame (m_ext_state, fun);
2735 std::unique_ptr<custom_edge_info> edge_info = NULL;
2737 if (lookup_attribute ("tainted_args", DECL_ATTRIBUTES (fun->decl)))
2739 if (mark_params_as_tainted (&state, fun->decl, m_ext_state))
2740 edge_info = make_unique<tainted_args_function_info> (fun->decl);
2746 exploded_node *enode = get_or_create_node (point, state, NULL);
2750 add_edge (m_origin, enode, NULL, std::move (edge_info));
2752 m_functions_with_enodes.add (fun);
2757 /* Get or create an exploded_node for (POINT, STATE).
2758 If a new node is created, it is added to the worklist.
2760 Use ENODE_FOR_DIAG, a pre-existing enode, for any diagnostics
2761 that need to be emitted (e.g. when purging state *before* we have
2765 exploded_graph::get_or_create_node (const program_point &point,
2766 const program_state &state,
2767 exploded_node *enode_for_diag)
2769 logger * const logger = get_logger ();
2774 pretty_printer *pp = logger->get_printer ();
2775 logger->start_log_line ();
2776 pp_string (pp, "point: ");
2777 point.print (pp, f);
2778 logger->end_log_line ();
2779 logger->start_log_line ();
2780 pp_string (pp, "state: ");
2781 state.dump_to_pp (m_ext_state, true, false, pp);
2782 logger->end_log_line ();
2785 /* Stop exploring paths for which we don't know how to effectively
2790 logger->log ("invalid state; not creating node");
2794 auto_cfun sentinel (point.get_function ());
2796 state.validate (get_ext_state ());
2798 //state.dump (get_ext_state ());
2800 /* Prune state to try to improve the chances of a cache hit,
2801 avoiding generating redundant nodes. */
2802 uncertainty_t uncertainty;
2803 program_state pruned_state
2804 = state.prune_for_point (*this, point, enode_for_diag, &uncertainty);
2806 pruned_state.validate (get_ext_state ());
2808 //pruned_state.dump (get_ext_state ());
2812 pretty_printer *pp = logger->get_printer ();
2813 logger->start_log_line ();
2814 pp_string (pp, "pruned_state: ");
2815 pruned_state.dump_to_pp (m_ext_state, true, false, pp);
2816 logger->end_log_line ();
2817 pruned_state.m_region_model->dump_to_pp (logger->get_printer (), true,
2821 stats *per_fn_stats = get_or_create_function_stats (point.get_function ());
2824 = &get_or_create_per_call_string_data (point.get_call_string ())->m_stats;
2826 point_and_state ps (point, pruned_state);
2827 ps.validate (m_ext_state);
2828 if (exploded_node **slot = m_point_and_state_to_node.get (&ps))
2830 /* An exploded_node for PS already exists. */
2832 logger->log ("reused EN: %i", (*slot)->m_index);
2833 m_global_stats.m_node_reuse_count++;
2834 per_fn_stats->m_node_reuse_count++;
2835 per_cs_stats->m_node_reuse_count++;
2839 per_program_point_data *per_point_data
2840 = get_or_create_per_program_point_data (point);
2842 /* Consider merging state with another enode at this program_point. */
2843 if (flag_analyzer_state_merge)
2845 exploded_node *existing_enode;
2847 FOR_EACH_VEC_ELT (per_point_data->m_enodes, i, existing_enode)
2850 logger->log ("considering merging with existing EN: %i for point",
2851 existing_enode->m_index);
2852 gcc_assert (existing_enode->get_point () == point);
2853 const program_state &existing_state = existing_enode->get_state ();
2855 /* This merges successfully within the loop. */
2857 program_state merged_state (m_ext_state);
2858 if (pruned_state.can_merge_with_p (existing_state, m_ext_state, point,
2861 merged_state.validate (m_ext_state);
2863 logger->log ("merging new state with that of EN: %i",
2864 existing_enode->m_index);
2866 /* Try again for a cache hit.
2867 Whether we get one or not, merged_state's value_ids have no
2868 relationship to those of the input state, and thus to those
2869 of CHANGE, so we must purge any svalue_ids from *CHANGE. */
2870 ps.set_state (merged_state);
2872 if (exploded_node **slot = m_point_and_state_to_node.get (&ps))
2874 /* An exploded_node for PS already exists. */
2876 logger->log ("reused EN: %i", (*slot)->m_index);
2877 m_global_stats.m_node_reuse_after_merge_count++;
2878 per_fn_stats->m_node_reuse_after_merge_count++;
2879 per_cs_stats->m_node_reuse_after_merge_count++;
2885 logger->log ("not merging new state with that of EN: %i",
2886 existing_enode->m_index);
2890 /* Impose a limit on the number of enodes per program point, and
2891 simply stop if we exceed it. */
2892 if ((int)per_point_data->m_enodes.length ()
2893 >= param_analyzer_max_enodes_per_program_point)
2896 point.print (&pp, format (false));
2897 print_enode_indices (&pp, per_point_data->m_enodes);
2899 logger->log ("not creating enode; too many at program point: %s",
2900 pp_formatted_text (&pp));
2901 warning_at (point.get_location (), OPT_Wanalyzer_too_complex,
2902 "terminating analysis for this program point: %s",
2903 pp_formatted_text (&pp));
2904 per_point_data->m_excess_enodes++;
2908 ps.validate (m_ext_state);
2910 /* An exploded_node for "ps" doesn't already exist; create one. */
2911 exploded_node *node = new exploded_node (ps, m_nodes.length ());
2913 m_point_and_state_to_node.put (node->get_ps_key (), node);
2915 /* Update per-program_point data. */
2916 per_point_data->m_enodes.safe_push (node);
2918 const enum point_kind node_pk = node->get_point ().get_kind ();
2919 m_global_stats.m_num_nodes[node_pk]++;
2920 per_fn_stats->m_num_nodes[node_pk]++;
2921 per_cs_stats->m_num_nodes[node_pk]++;
2923 if (node_pk == PK_AFTER_SUPERNODE)
2924 m_PK_AFTER_SUPERNODE_per_snode[point.get_supernode ()->m_index]++;
2929 pretty_printer *pp = logger->get_printer ();
2930 logger->log ("created EN: %i", node->m_index);
2931 logger->start_log_line ();
2932 pp_string (pp, "point: ");
2933 point.print (pp, f);
2934 logger->end_log_line ();
2935 logger->start_log_line ();
2936 pp_string (pp, "pruned_state: ");
2937 pruned_state.dump_to_pp (m_ext_state, true, false, pp);
2938 logger->end_log_line ();
2941 /* Add the new node to the worlist. */
2942 m_worklist.add_node (node);
2946 /* Add an exploded_edge from SRC to DEST, recording its association
2947 with SEDGE (which may be NULL), and, if non-NULL, taking ownership
2949 Return the newly-created eedge. */
2952 exploded_graph::add_edge (exploded_node *src, exploded_node *dest,
2953 const superedge *sedge,
2954 std::unique_ptr<custom_edge_info> custom_info)
2957 get_logger ()->log ("creating edge EN: %i -> EN: %i",
2958 src->m_index, dest->m_index);
2959 exploded_edge *e = new exploded_edge (src, dest, sedge,
2960 std::move (custom_info));
2961 digraph<eg_traits>::add_edge (e);
2965 /* Ensure that this graph has per-program_point-data for POINT;
2966 borrow a pointer to it. */
2968 per_program_point_data *
2970 get_or_create_per_program_point_data (const program_point &point)
2972 if (per_program_point_data **slot = m_per_point_data.get (&point))
2975 per_program_point_data *per_point_data = new per_program_point_data (point);
2976 m_per_point_data.put (&per_point_data->m_key, per_point_data);
2977 return per_point_data;
2980 /* Get this graph's per-program-point-data for POINT if there is any,
2983 per_program_point_data *
2984 exploded_graph::get_per_program_point_data (const program_point &point) const
2986 if (per_program_point_data **slot
2987 = const_cast <point_map_t &> (m_per_point_data).get (&point))
2993 /* Ensure that this graph has per-call_string-data for CS;
2994 borrow a pointer to it. */
2996 per_call_string_data *
2997 exploded_graph::get_or_create_per_call_string_data (const call_string &cs)
2999 if (per_call_string_data **slot = m_per_call_string_data.get (&cs))
3002 per_call_string_data *data = new per_call_string_data (cs, m_sg.num_nodes ());
3003 m_per_call_string_data.put (&data->m_key,
3008 /* Ensure that this graph has per-function-data for FUN;
3009 borrow a pointer to it. */
3012 exploded_graph::get_or_create_per_function_data (function *fun)
3014 if (per_function_data **slot = m_per_function_data.get (fun))
3017 per_function_data *data = new per_function_data ();
3018 m_per_function_data.put (fun, data);
3022 /* Get this graph's per-function-data for FUN if there is any,
3026 exploded_graph::get_per_function_data (function *fun) const
3028 if (per_function_data **slot
3029 = const_cast <per_function_data_t &> (m_per_function_data).get (fun))
3035 /* Return true if FUN should be traversed directly, rather than only as
3036 called via other functions. */
3039 toplevel_function_p (function *fun, logger *logger)
3041 /* Don't directly traverse into functions that have an "__analyzer_"
3042 prefix. Doing so is useful for the analyzer test suite, allowing
3043 us to have functions that are called in traversals, but not directly
3044 explored, thus testing how the analyzer handles calls and returns.
3045 With this, we can have DejaGnu directives that cover just the case
3046 of where a function is called by another function, without generating
3047 excess messages from the case of the first function being traversed
3049 #define ANALYZER_PREFIX "__analyzer_"
3050 if (!strncmp (IDENTIFIER_POINTER (DECL_NAME (fun->decl)), ANALYZER_PREFIX,
3051 strlen (ANALYZER_PREFIX)))
3054 logger->log ("not traversing %qE (starts with %qs)",
3055 fun->decl, ANALYZER_PREFIX);
3060 logger->log ("traversing %qE (all checks passed)", fun->decl);
3065 /* Custom event for use by tainted_call_info when a callback field has been
3066 marked with __attribute__((tainted_args)), for labelling the field. */
3068 class tainted_args_field_custom_event : public custom_event
3071 tainted_args_field_custom_event (tree field)
3072 : custom_event (DECL_SOURCE_LOCATION (field), NULL_TREE, 0),
3077 label_text get_desc (bool can_colorize) const final override
3079 return make_label_text (can_colorize,
3081 " is marked with %<__attribute__((tainted_args))%>",
3082 m_field, DECL_CONTEXT (m_field));
3089 /* Custom event for use by tainted_call_info when a callback field has been
3090 marked with __attribute__((tainted_args)), for labelling the function used
3091 in that callback. */
3093 class tainted_args_callback_custom_event : public custom_event
3096 tainted_args_callback_custom_event (location_t loc, tree fndecl, int depth,
3098 : custom_event (loc, fndecl, depth),
3103 label_text get_desc (bool can_colorize) const final override
3105 return make_label_text (can_colorize,
3106 "function %qE used as initializer for field %qE"
3107 " marked with %<__attribute__((tainted_args))%>",
3108 get_fndecl (), m_field);
3115 /* Custom edge info for use when adding a function used by a callback field
3116 marked with '__attribute__((tainted_args))'. */
3118 class tainted_args_call_info : public custom_edge_info
3121 tainted_args_call_info (tree field, tree fndecl, location_t loc)
3122 : m_field (field), m_fndecl (fndecl), m_loc (loc)
3125 void print (pretty_printer *pp) const final override
3127 pp_string (pp, "call to tainted field");
3130 bool update_model (region_model *,
3131 const exploded_edge *,
3132 region_model_context *) const final override
3138 void add_events_to_path (checker_path *emission_path,
3139 const exploded_edge &) const final override
3141 /* Show the field in the struct declaration, e.g.
3142 "(1) field 'store' is marked with '__attribute__((tainted_args))'" */
3143 emission_path->add_event
3144 (make_unique<tainted_args_field_custom_event> (m_field));
3146 /* Show the callback in the initializer
3148 "(2) function 'gadget_dev_desc_UDC_store' used as initializer
3149 for field 'store' marked with '__attribute__((tainted_args))'". */
3150 emission_path->add_event
3151 (make_unique<tainted_args_callback_custom_event> (m_loc, m_fndecl,
3161 /* Given an initializer at LOC for FIELD marked with
3162 '__attribute__((tainted_args))' initialized with FNDECL, add an
3163 entrypoint to FNDECL to EG (and to its worklist) where the params to
3164 FNDECL are marked as tainted. */
3167 add_tainted_args_callback (exploded_graph *eg, tree field, tree fndecl,
3170 logger *logger = eg->get_logger ();
3174 if (!gimple_has_body_p (fndecl))
3177 const extrinsic_state &ext_state = eg->get_ext_state ();
3179 function *fun = DECL_STRUCT_FUNCTION (fndecl);
3183 = program_point::from_function_entry (*ext_state.get_model_manager (),
3184 eg->get_supergraph (), fun);
3185 program_state state (ext_state);
3186 state.push_frame (ext_state, fun);
3188 if (!mark_params_as_tainted (&state, fndecl, ext_state))
3194 exploded_node *enode = eg->get_or_create_node (point, state, NULL);
3198 logger->log ("created EN %i for tainted_args %qE entrypoint",
3199 enode->m_index, fndecl);
3202 logger->log ("did not create enode for tainted_args %qE entrypoint",
3208 eg->add_edge (eg->get_origin (), enode, NULL,
3209 make_unique<tainted_args_call_info> (field, fndecl, loc));
3212 /* Callback for walk_tree for finding callbacks within initializers;
3213 ensure that any callback initializer where the corresponding field is
3214 marked with '__attribute__((tainted_args))' is treated as an entrypoint
3215 to the analysis, special-casing that the inputs to the callback are
3219 add_any_callbacks (tree *tp, int *, void *data)
3221 exploded_graph *eg = (exploded_graph *)data;
3222 if (TREE_CODE (*tp) == CONSTRUCTOR)
3224 /* Find fields with the "tainted_args" attribute.
3225 walk_tree only walks the values, not the index values;
3226 look at the index values. */
3227 unsigned HOST_WIDE_INT idx;
3228 constructor_elt *ce;
3230 for (idx = 0; vec_safe_iterate (CONSTRUCTOR_ELTS (*tp), idx, &ce);
3232 if (ce->index && TREE_CODE (ce->index) == FIELD_DECL)
3233 if (lookup_attribute ("tainted_args", DECL_ATTRIBUTES (ce->index)))
3235 tree value = ce->value;
3236 if (TREE_CODE (value) == ADDR_EXPR
3237 && TREE_CODE (TREE_OPERAND (value, 0)) == FUNCTION_DECL)
3238 add_tainted_args_callback (eg, ce->index,
3239 TREE_OPERAND (value, 0),
3240 EXPR_LOCATION (value));
3247 /* Add initial nodes to EG, with entrypoints for externally-callable
3251 exploded_graph::build_initial_worklist ()
3253 logger * const logger = get_logger ();
3257 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
3259 function *fun = node->get_fun ();
3260 if (!toplevel_function_p (fun, logger))
3262 exploded_node *enode = add_function_entry (fun);
3266 logger->log ("created EN %i for %qE entrypoint",
3267 enode->m_index, fun->decl);
3269 logger->log ("did not create enode for %qE entrypoint", fun->decl);
3273 /* Find callbacks that are reachable from global initializers. */
3274 varpool_node *vpnode;
3275 FOR_EACH_VARIABLE (vpnode)
3277 tree decl = vpnode->decl;
3278 tree init = DECL_INITIAL (decl);
3281 walk_tree (&init, add_any_callbacks, this, NULL);
3285 /* The main loop of the analysis.
3286 Take freshly-created exploded_nodes from the worklist, calling
3287 process_node on them to explore the <point, state> graph.
3288 Add edges to their successors, potentially creating new successors
3289 (which are also added to the worklist). */
3292 exploded_graph::process_worklist ()
3294 logger * const logger = get_logger ();
3296 auto_timevar tv (TV_ANALYZER_WORKLIST);
3298 while (m_worklist.length () > 0)
3300 exploded_node *node = m_worklist.take_next ();
3301 gcc_assert (node->get_status () == exploded_node::STATUS_WORKLIST);
3302 gcc_assert (node->m_succs.length () == 0
3303 || node == m_origin);
3306 logger->log ("next to process: EN: %i", node->m_index);
3308 /* If we have a run of nodes that are before-supernode, try merging and
3309 processing them together, rather than pairwise or individually. */
3310 if (flag_analyzer_state_merge && node != m_origin)
3311 if (maybe_process_run_of_before_supernode_enodes (node))
3314 /* Avoid exponential explosions of nodes by attempting to merge
3315 nodes that are at the same program point and which have
3316 sufficiently similar state. */
3317 if (flag_analyzer_state_merge && node != m_origin)
3318 if (exploded_node *node_2 = m_worklist.peek_next ())
3320 gcc_assert (node_2->get_status ()
3321 == exploded_node::STATUS_WORKLIST);
3322 gcc_assert (node->m_succs.length () == 0);
3323 gcc_assert (node_2->m_succs.length () == 0);
3325 gcc_assert (node != node_2);
3328 logger->log ("peek worklist: EN: %i", node_2->m_index);
3330 if (node->get_point () == node_2->get_point ())
3332 const program_point &point = node->get_point ();
3336 pretty_printer *pp = logger->get_printer ();
3337 logger->start_log_line ();
3339 ("got potential merge EN: %i and EN: %i at ",
3340 node->m_index, node_2->m_index);
3341 point.print (pp, f);
3342 logger->end_log_line ();
3344 const program_state &state = node->get_state ();
3345 const program_state &state_2 = node_2->get_state ();
3347 /* They shouldn't be equal, or we wouldn't have two
3349 gcc_assert (state != state_2);
3351 program_state merged_state (m_ext_state);
3352 if (state.can_merge_with_p (state_2, m_ext_state,
3353 point, &merged_state))
3356 logger->log ("merging EN: %i and EN: %i",
3357 node->m_index, node_2->m_index);
3359 if (merged_state == state)
3361 /* Then merge node_2 into node by adding an edge. */
3362 add_edge (node_2, node, NULL);
3364 /* Remove node_2 from the worklist. */
3365 m_worklist.take_next ();
3366 node_2->set_status (exploded_node::STATUS_MERGER);
3368 /* Continue processing "node" below. */
3370 else if (merged_state == state_2)
3372 /* Then merge node into node_2, and leave node_2
3373 in the worklist, to be processed on the next
3375 add_edge (node, node_2, NULL);
3376 node->set_status (exploded_node::STATUS_MERGER);
3381 /* We have a merged state that differs from
3382 both state and state_2. */
3384 /* Remove node_2 from the worklist. */
3385 m_worklist.take_next ();
3387 /* Create (or get) an exploded node for the merged
3388 states, adding to the worklist. */
3389 exploded_node *merged_enode
3390 = get_or_create_node (node->get_point (),
3391 merged_state, node);
3392 if (merged_enode == NULL)
3396 logger->log ("merged EN: %i and EN: %i into EN: %i",
3397 node->m_index, node_2->m_index,
3398 merged_enode->m_index);
3400 /* "node" and "node_2" have both now been removed
3401 from the worklist; we should not process them.
3403 "merged_enode" may be a new node; if so it will be
3404 processed in a subsequent iteration.
3405 Alternatively, "merged_enode" could be an existing
3406 node; one way the latter can
3407 happen is if we end up merging a succession of
3408 similar nodes into one. */
3410 /* If merged_node is one of the two we were merging,
3411 add it back to the worklist to ensure it gets
3414 Add edges from the merged nodes to it (but not a
3416 if (merged_enode == node)
3417 m_worklist.add_node (merged_enode);
3420 add_edge (node, merged_enode, NULL);
3421 node->set_status (exploded_node::STATUS_MERGER);
3424 if (merged_enode == node_2)
3425 m_worklist.add_node (merged_enode);
3428 add_edge (node_2, merged_enode, NULL);
3429 node_2->set_status (exploded_node::STATUS_MERGER);
3436 /* TODO: should we attempt more than two nodes,
3437 or just do pairs of nodes? (and hope that we get
3438 a cascade of mergers). */
3442 process_node (node);
3445 /* Impose a hard limit on the number of exploded nodes, to ensure
3446 that the analysis terminates in the face of pathological state
3447 explosion (or bugs).
3449 Specifically, the limit is on the number of PK_AFTER_SUPERNODE
3450 exploded nodes, looking at supernode exit events.
3452 We use exit rather than entry since there can be multiple
3453 entry ENs, one per phi; the number of PK_AFTER_SUPERNODE ought
3454 to be equivalent to the number of supernodes multiplied by the
3455 number of states. */
3456 const int limit = m_sg.num_nodes () * param_analyzer_bb_explosion_factor;
3457 if (m_global_stats.m_num_nodes[PK_AFTER_SUPERNODE] > limit)
3460 logger->log ("bailing out; too many nodes");
3461 warning_at (node->get_point ().get_location (),
3462 OPT_Wanalyzer_too_complex,
3463 "analysis bailed out early"
3464 " (%i 'after-snode' enodes; %i enodes)",
3465 m_global_stats.m_num_nodes[PK_AFTER_SUPERNODE],
3472 /* Attempt to process a consecutive run of sufficiently-similar nodes in
3473 the worklist at a CFG join-point (having already popped ENODE from the
3474 head of the worklist).
3476 If ENODE's point is of the form (before-supernode, SNODE) and the next
3477 nodes in the worklist are a consecutive run of enodes of the same form,
3478 for the same supernode as ENODE (but potentially from different in-edges),
3479 process them all together, setting their status to STATUS_BULK_MERGED,
3481 Otherwise, return false, in which case ENODE must be processed in the
3484 When processing them all together, generate successor states based
3485 on phi nodes for the appropriate CFG edges, and then attempt to merge
3486 these states into a minimal set of merged successor states, partitioning
3487 the inputs by merged successor state.
3489 Create new exploded nodes for all of the merged states, and add edges
3490 connecting the input enodes to the corresponding merger exploded nodes.
3492 We hope we have a much smaller number of merged successor states
3493 compared to the number of input enodes - ideally just one,
3494 if all successor states can be merged.
3496 Processing and merging many together as one operation rather than as
3497 pairs avoids scaling issues where per-pair mergers could bloat the
3498 graph with merger nodes (especially so after switch statements). */
3502 maybe_process_run_of_before_supernode_enodes (exploded_node *enode)
3504 /* A struct for tracking per-input state. */
3507 item (exploded_node *input_enode)
3508 : m_input_enode (input_enode),
3509 m_processed_state (input_enode->get_state ()),
3513 exploded_node *m_input_enode;
3514 program_state m_processed_state;
3518 gcc_assert (enode->get_status () == exploded_node::STATUS_WORKLIST);
3519 gcc_assert (enode->m_succs.length () == 0);
3521 const program_point &point = enode->get_point ();
3523 if (point.get_kind () != PK_BEFORE_SUPERNODE)
3526 const supernode *snode = point.get_supernode ();
3528 logger * const logger = get_logger ();
3531 /* Find a run of enodes in the worklist that are before the same supernode,
3532 but potentially from different in-edges. */
3533 auto_vec <exploded_node *> enodes;
3534 enodes.safe_push (enode);
3535 while (exploded_node *enode_2 = m_worklist.peek_next ())
3537 gcc_assert (enode_2->get_status ()
3538 == exploded_node::STATUS_WORKLIST);
3539 gcc_assert (enode_2->m_succs.length () == 0);
3541 const program_point &point_2 = enode_2->get_point ();
3543 if (point_2.get_kind () == PK_BEFORE_SUPERNODE
3544 && point_2.get_supernode () == snode
3545 && &point_2.get_call_string () == &point.get_call_string ())
3547 enodes.safe_push (enode_2);
3548 m_worklist.take_next ();
3554 /* If the only node is ENODE, then give up. */
3555 if (enodes.length () == 1)
3559 logger->log ("got run of %i enodes for SN: %i",
3560 enodes.length (), snode->m_index);
3562 /* All of these enodes have a shared successor point (even if they
3563 were for different in-edges). */
3564 program_point next_point (point.get_next ());
3566 /* Calculate the successor state for each enode in enodes. */
3567 auto_delete_vec<item> items (enodes.length ());
3569 exploded_node *iter_enode;
3570 FOR_EACH_VEC_ELT (enodes, i, iter_enode)
3572 item *it = new item (iter_enode);
3573 items.quick_push (it);
3574 const program_state &state = iter_enode->get_state ();
3575 program_state *next_state = &it->m_processed_state;
3576 next_state->validate (m_ext_state);
3577 const program_point &iter_point = iter_enode->get_point ();
3578 if (const superedge *iter_sedge = iter_point.get_from_edge ())
3580 uncertainty_t uncertainty;
3581 impl_region_model_context ctxt (*this, iter_enode,
3583 &uncertainty, NULL, NULL);
3584 const cfg_superedge *last_cfg_superedge
3585 = iter_sedge->dyn_cast_cfg_superedge ();
3586 if (last_cfg_superedge)
3587 next_state->m_region_model->update_for_phis
3588 (snode, last_cfg_superedge, &ctxt);
3590 next_state->validate (m_ext_state);
3593 /* Attempt to partition the items into a set of merged states.
3594 We hope we have a much smaller number of merged states
3595 compared to the number of input enodes - ideally just one,
3596 if all can be merged. */
3597 auto_delete_vec <program_state> merged_states;
3598 auto_vec<item *> first_item_for_each_merged_state;
3600 FOR_EACH_VEC_ELT (items, i, it)
3602 const program_state &it_state = it->m_processed_state;
3603 program_state *merged_state;
3604 unsigned iter_merger_idx;
3605 FOR_EACH_VEC_ELT (merged_states, iter_merger_idx, merged_state)
3607 merged_state->validate (m_ext_state);
3608 program_state merge (m_ext_state);
3609 if (it_state.can_merge_with_p (*merged_state, m_ext_state,
3610 next_point, &merge))
3612 *merged_state = merge;
3613 merged_state->validate (m_ext_state);
3614 it->m_merger_idx = iter_merger_idx;
3616 logger->log ("reusing merger state %i for item %i (EN: %i)",
3617 it->m_merger_idx, i, it->m_input_enode->m_index);
3621 /* If it couldn't be merged with any existing merged_states,
3622 create a new one. */
3623 if (it->m_merger_idx == -1)
3625 it->m_merger_idx = merged_states.length ();
3626 merged_states.safe_push (new program_state (it_state));
3627 first_item_for_each_merged_state.safe_push (it);
3629 logger->log ("using new merger state %i for item %i (EN: %i)",
3630 it->m_merger_idx, i, it->m_input_enode->m_index);
3633 gcc_assert (it->m_merger_idx >= 0);
3634 gcc_assert ((unsigned)it->m_merger_idx < merged_states.length ());
3637 /* Create merger nodes. */
3638 auto_vec<exploded_node *> next_enodes (merged_states.length ());
3639 program_state *merged_state;
3640 FOR_EACH_VEC_ELT (merged_states, i, merged_state)
3642 exploded_node *src_enode
3643 = first_item_for_each_merged_state[i]->m_input_enode;
3645 = get_or_create_node (next_point, *merged_state, src_enode);
3646 /* "next" could be NULL; we handle that when adding the edges below. */
3647 next_enodes.quick_push (next);
3651 logger->log ("using EN: %i for merger state %i", next->m_index, i);
3653 logger->log ("using NULL enode for merger state %i", i);
3657 /* Create edges from each input enode to the appropriate successor enode.
3658 Update the status of the now-processed input enodes. */
3659 FOR_EACH_VEC_ELT (items, i, it)
3661 exploded_node *next = next_enodes[it->m_merger_idx];
3663 add_edge (it->m_input_enode, next, NULL);
3664 it->m_input_enode->set_status (exploded_node::STATUS_BULK_MERGED);
3668 logger->log ("merged %i in-enodes into %i out-enode(s) at SN: %i",
3669 items.length (), merged_states.length (), snode->m_index);
3674 /* Return true if STMT must appear at the start of its exploded node, and
3675 thus we can't consolidate its effects within a run of other statements,
3676 where PREV_STMT was the previous statement. */
3679 stmt_requires_new_enode_p (const gimple *stmt,
3680 const gimple *prev_stmt)
3682 if (const gcall *call = dyn_cast <const gcall *> (stmt))
3684 /* Stop consolidating at calls to
3685 "__analyzer_dump_exploded_nodes", so they always appear at the
3686 start of an exploded_node. */
3687 if (is_special_named_call_p (call, "__analyzer_dump_exploded_nodes",
3691 /* sm-signal.cc injects an additional custom eedge at "signal" calls
3692 from the registration enode to the handler enode, separate from the
3693 regular next state, which defeats the "detect state change" logic
3694 in process_node. Work around this via special-casing, to ensure
3695 we split the enode immediately before any "signal" call. */
3696 if (is_special_named_call_p (call, "signal", 2))
3700 /* If we had a PREV_STMT with an unknown location, and this stmt
3701 has a known location, then if a state change happens here, it
3702 could be consolidated into PREV_STMT, giving us an event with
3703 no location. Ensure that STMT gets its own exploded_node to
3705 if (get_pure_location (prev_stmt->location) == UNKNOWN_LOCATION
3706 && get_pure_location (stmt->location) != UNKNOWN_LOCATION)
3712 /* Return true if OLD_STATE and NEW_STATE are sufficiently different that
3713 we should split enodes and create an exploded_edge separating them
3714 (which makes it easier to identify state changes of intereset when
3715 constructing checker_paths). */
3718 state_change_requires_new_enode_p (const program_state &old_state,
3719 const program_state &new_state)
3721 /* Changes in dynamic extents signify creations of heap/alloca regions
3722 and resizings of heap regions; likely to be of interest in
3723 diagnostic paths. */
3724 if (old_state.m_region_model->get_dynamic_extents ()
3725 != new_state.m_region_model->get_dynamic_extents ())
3728 /* Changes in sm-state are of interest. */
3731 FOR_EACH_VEC_ELT (old_state.m_checker_states, sm_idx, smap)
3733 const sm_state_map *old_smap = old_state.m_checker_states[sm_idx];
3734 const sm_state_map *new_smap = new_state.m_checker_states[sm_idx];
3735 if (*old_smap != *new_smap)
3742 /* Create enodes and eedges for the function calls that doesn't have an
3743 underlying call superedge.
3745 Such case occurs when GCC's middle end didn't know which function to
3746 call but the analyzer does (with the help of current state).
3748 Some example such calls are dynamically dispatched calls to virtual
3749 functions or calls that happen via function pointer. */
3752 exploded_graph::maybe_create_dynamic_call (const gcall *call,
3754 exploded_node *node,
3755 program_state next_state,
3756 program_point &next_point,
3757 uncertainty_t *uncertainty,
3762 const program_point *this_point = &node->get_point ();
3763 function *fun = DECL_STRUCT_FUNCTION (fn_decl);
3766 const supergraph &sg = this->get_supergraph ();
3767 supernode *sn_entry = sg.get_node_for_function_entry (fun);
3768 supernode *sn_exit = sg.get_node_for_function_exit (fun);
3770 program_point new_point
3771 = program_point::before_supernode (sn_entry,
3773 this_point->get_call_string ());
3775 new_point.push_to_call_stack (sn_exit,
3776 next_point.get_supernode());
3778 /* Impose a maximum recursion depth and don't analyze paths
3779 that exceed it further.
3780 This is something of a blunt workaround, but it only
3781 applies to recursion (and mutual recursion), not to
3782 general call stacks. */
3783 if (new_point.get_call_string ().calc_recursion_depth ()
3784 > param_analyzer_max_recursion_depth)
3787 logger->log ("rejecting call edge: recursion limit exceeded");
3791 next_state.push_call (*this, node, call, uncertainty);
3793 if (next_state.m_valid)
3796 logger->log ("Discovered call to %s [SN: %i -> SN: %i]",
3798 this_point->get_supernode ()->m_index,
3801 exploded_node *enode = get_or_create_node (new_point,
3805 add_edge (node,enode, NULL,
3806 make_unique<dynamic_call_info_t> (call));
3813 /* Subclass of path_context for use within exploded_graph::process_node,
3814 so that we can split states e.g. at "realloc" calls. */
3816 class impl_path_context : public path_context
3819 impl_path_context (const program_state *cur_state)
3820 : m_cur_state (cur_state),
3821 m_terminate_path (false)
3825 bool bifurcation_p () const
3827 return m_custom_eedge_infos.length () > 0;
3830 const program_state &get_state_at_bifurcation () const
3832 gcc_assert (m_state_at_bifurcation);
3833 return *m_state_at_bifurcation;
3837 bifurcate (std::unique_ptr<custom_edge_info> info) final override
3839 if (m_state_at_bifurcation)
3840 /* Verify that the state at bifurcation is consistent when we
3841 split into multiple out-edges. */
3842 gcc_assert (*m_state_at_bifurcation == *m_cur_state);
3844 /* Take a copy of the cur_state at the moment when bifurcation
3846 m_state_at_bifurcation
3847 = std::unique_ptr<program_state> (new program_state (*m_cur_state));
3849 /* Take ownership of INFO. */
3850 m_custom_eedge_infos.safe_push (info.release ());
3853 void terminate_path () final override
3855 m_terminate_path = true;
3858 bool terminate_path_p () const final override
3860 return m_terminate_path;
3863 const vec<custom_edge_info *> & get_custom_eedge_infos ()
3865 return m_custom_eedge_infos;
3869 const program_state *m_cur_state;
3871 /* Lazily-created copy of the state before the split. */
3872 std::unique_ptr<program_state> m_state_at_bifurcation;
3874 auto_vec <custom_edge_info *> m_custom_eedge_infos;
3876 bool m_terminate_path;
3879 /* A subclass of pending_diagnostic for complaining about jumps through NULL
3880 function pointers. */
3882 class jump_through_null : public pending_diagnostic_subclass<jump_through_null>
3885 jump_through_null (const gcall *call)
3889 const char *get_kind () const final override
3891 return "jump_through_null";
3894 bool operator== (const jump_through_null &other) const
3896 return m_call == other.m_call;
3899 int get_controlling_option () const final override
3901 return OPT_Wanalyzer_jump_through_null;
3904 bool emit (rich_location *rich_loc) final override
3906 return warning_at (rich_loc, get_controlling_option (),
3907 "jump through null pointer");
3910 label_text describe_final_event (const evdesc::final_event &ev) final override
3912 return ev.formatted_print ("jump through null pointer here");
3916 const gcall *m_call;
3919 /* The core of exploded_graph::process_worklist (the main analysis loop),
3920 handling one node in the worklist.
3922 Get successor <point, state> pairs for NODE, calling get_or_create on
3923 them, and adding an exploded_edge to each successors.
3925 Freshly-created nodes will be added to the worklist. */
3928 exploded_graph::process_node (exploded_node *node)
3930 logger * const logger = get_logger ();
3931 LOG_FUNC_1 (logger, "EN: %i", node->m_index);
3933 node->set_status (exploded_node::STATUS_PROCESSED);
3935 const program_point &point = node->get_point ();
3937 /* Update cfun and input_location in case of an ICE: make it easier to
3938 track down which source construct we're failing to handle. */
3939 auto_cfun sentinel (node->get_function ());
3940 const gimple *stmt = point.get_stmt ();
3942 input_location = stmt->location;
3944 const program_state &state = node->get_state ();
3947 pretty_printer *pp = logger->get_printer ();
3948 logger->start_log_line ();
3949 pp_string (pp, "point: ");
3950 point.print (pp, format (false));
3951 pp_string (pp, ", state: ");
3952 state.dump_to_pp (m_ext_state, true, false, pp);
3953 logger->end_log_line ();
3956 switch (point.get_kind ())
3961 /* This node exists to simplify finding the shortest path
3962 to an exploded_node. */
3965 case PK_BEFORE_SUPERNODE:
3967 program_state next_state (state);
3968 uncertainty_t uncertainty;
3970 if (point.get_from_edge ())
3972 impl_region_model_context ctxt (*this, node,
3973 &state, &next_state,
3974 &uncertainty, NULL, NULL);
3975 const cfg_superedge *last_cfg_superedge
3976 = point.get_from_edge ()->dyn_cast_cfg_superedge ();
3977 if (last_cfg_superedge)
3978 next_state.m_region_model->update_for_phis
3979 (node->get_supernode (),
3982 program_state::detect_leaks (state, next_state, NULL,
3983 get_ext_state (), &ctxt);
3986 program_point next_point (point.get_next ());
3987 exploded_node *next = get_or_create_node (next_point, next_state, node);
3989 add_edge (node, next, NULL);
3992 case PK_BEFORE_STMT:
3994 /* Determine the effect of a run of one or more statements
3995 within one supernode, generating an edge to the program_point
3996 after the last statement that's processed.
3998 Stop iterating statements and thus consolidating into one enode
4000 - reaching the end of the statements in the supernode
4001 - if an sm-state-change occurs (so that it gets its own
4003 - if "-fanalyzer-fine-grained" is active
4004 - encountering certain statements must appear at the start of
4005 their enode (for which stmt_requires_new_enode_p returns true)
4007 Update next_state in-place, to get the result of the one
4008 or more stmts that are processed.
4010 Split the node in-place if an sm-state-change occurs, so that
4011 the sm-state-change occurs on an edge where the src enode has
4012 exactly one stmt, the one that caused the change. */
4013 program_state next_state (state);
4015 impl_path_context path_ctxt (&next_state);
4017 uncertainty_t uncertainty;
4018 const supernode *snode = point.get_supernode ();
4020 const gimple *prev_stmt = NULL;
4021 for (stmt_idx = point.get_stmt_idx ();
4022 stmt_idx < snode->m_stmts.length ();
4025 const gimple *stmt = snode->m_stmts[stmt_idx];
4027 if (stmt_idx > point.get_stmt_idx ())
4028 if (stmt_requires_new_enode_p (stmt, prev_stmt))
4035 program_state old_state (next_state);
4037 /* Process the stmt. */
4038 exploded_node::on_stmt_flags flags
4039 = node->on_stmt (*this, snode, stmt, &next_state, &uncertainty,
4041 node->m_num_processed_stmts++;
4043 /* If flags.m_terminate_path, stop analyzing; any nodes/edges
4044 will have been added by on_stmt (e.g. for handling longjmp). */
4045 if (flags.m_terminate_path)
4048 if (next_state.m_region_model)
4050 impl_region_model_context ctxt (*this, node,
4051 &old_state, &next_state,
4052 &uncertainty, NULL, stmt);
4053 program_state::detect_leaks (old_state, next_state, NULL,
4054 get_ext_state (), &ctxt);
4057 unsigned next_idx = stmt_idx + 1;
4058 program_point next_point
4059 = (next_idx < point.get_supernode ()->m_stmts.length ()
4060 ? program_point::before_stmt (point.get_supernode (), next_idx,
4061 point.get_call_string ())
4062 : program_point::after_supernode (point.get_supernode (),
4063 point.get_call_string ()));
4064 next_state = next_state.prune_for_point (*this, next_point, node,
4067 if (flag_analyzer_fine_grained
4068 || state_change_requires_new_enode_p (old_state, next_state)
4069 || path_ctxt.bifurcation_p ()
4070 || path_ctxt.terminate_path_p ())
4072 program_point split_point
4073 = program_point::before_stmt (point.get_supernode (),
4075 point.get_call_string ());
4076 if (split_point != node->get_point ())
4078 /* If we're not at the start of NODE, split the enode at
4079 this stmt, so we have:
4081 so that when split_enode is processed the next edge
4084 and any state change will effectively occur on that
4085 latter edge, and split_enode will contain just stmt. */
4087 logger->log ("getting split_enode");
4088 exploded_node *split_enode
4089 = get_or_create_node (split_point, old_state, node);
4092 /* "stmt" will be reprocessed when split_enode is
4094 node->m_num_processed_stmts--;
4096 logger->log ("creating edge to split_enode");
4097 add_edge (node, split_enode, NULL);
4101 /* If we're at the start of NODE, stop iterating,
4102 so that an edge will be created from NODE to
4103 (next_point, next_state) below. */
4107 unsigned next_idx = stmt_idx + 1;
4108 program_point next_point
4109 = (next_idx < point.get_supernode ()->m_stmts.length ()
4110 ? program_point::before_stmt (point.get_supernode (), next_idx,
4111 point.get_call_string ())
4112 : program_point::after_supernode (point.get_supernode (),
4113 point.get_call_string ()));
4114 if (path_ctxt.terminate_path_p ())
4117 logger->log ("not adding node: terminating path");
4122 = get_or_create_node (next_point, next_state, node);
4124 add_edge (node, next, NULL);
4127 /* If we have custom edge infos, "bifurcate" the state
4128 accordingly, potentially creating a new state/enode/eedge
4129 instances. For example, to handle a "realloc" call, we
4130 might split into 3 states, for the "failure",
4131 "resizing in place", and "moving to a new buffer" cases. */
4132 for (auto edge_info_iter : path_ctxt.get_custom_eedge_infos ())
4134 /* Take ownership of the edge infos from the path_ctxt. */
4135 std::unique_ptr<custom_edge_info> edge_info (edge_info_iter);
4138 logger->start_log_line ();
4139 logger->log_partial ("bifurcating for edge: ");
4140 edge_info->print (logger->get_printer ());
4141 logger->end_log_line ();
4143 program_state bifurcated_new_state
4144 (path_ctxt.get_state_at_bifurcation ());
4146 /* Apply edge_info to state. */
4147 impl_region_model_context
4148 bifurcation_ctxt (*this,
4149 node, // enode_for_diag
4150 &path_ctxt.get_state_at_bifurcation (),
4151 &bifurcated_new_state,
4152 NULL, // uncertainty_t *uncertainty
4153 NULL, // path_context *path_ctxt
4155 if (edge_info->update_state (&bifurcated_new_state,
4156 NULL, /* no exploded_edge yet. */
4159 exploded_node *next2
4160 = get_or_create_node (next_point, bifurcated_new_state, node);
4162 add_edge (node, next2, NULL, std::move (edge_info));
4167 logger->log ("infeasible state, not adding node");
4172 case PK_AFTER_SUPERNODE:
4174 bool found_a_superedge = false;
4175 bool is_an_exit_block = false;
4176 /* If this is an EXIT BB, detect leaks, and potentially
4177 create a function summary. */
4178 if (point.get_supernode ()->return_p ())
4180 is_an_exit_block = true;
4181 node->detect_leaks (*this);
4182 if (flag_analyzer_call_summaries
4183 && point.get_call_string ().empty_p ())
4185 /* TODO: create function summary
4186 There can be more than one; each corresponds to a different
4187 final enode in the function. */
4190 pretty_printer *pp = logger->get_printer ();
4191 logger->start_log_line ();
4193 ("would create function summary for %qE; state: ",
4194 point.get_fndecl ());
4195 state.dump_to_pp (m_ext_state, true, false, pp);
4196 logger->end_log_line ();
4198 per_function_data *per_fn_data
4199 = get_or_create_per_function_data (point.get_function ());
4200 per_fn_data->add_call_summary (node);
4203 /* Traverse into successors of the supernode. */
4206 FOR_EACH_VEC_ELT (point.get_supernode ()->m_succs, i, succ)
4208 found_a_superedge = true;
4211 label_text succ_desc (succ->get_description (false));
4212 logger->log ("considering SN: %i -> SN: %i (%s)",
4213 succ->m_src->m_index, succ->m_dest->m_index,
4217 program_point next_point
4218 = program_point::before_supernode (succ->m_dest, succ,
4219 point.get_call_string ());
4220 program_state next_state (state);
4221 uncertainty_t uncertainty;
4223 /* Make use the current state and try to discover and analyse
4224 indirect function calls (a call that doesn't have an underlying
4225 cgraph edge representing call).
4227 Some examples of such calls are virtual function calls
4228 and calls that happen via a function pointer. */
4229 if (succ->m_kind == SUPEREDGE_INTRAPROCEDURAL_CALL
4230 && !(succ->get_any_callgraph_edge ()))
4233 = point.get_supernode ()->get_final_call ();
4235 impl_region_model_context ctxt (*this,
4243 region_model *model = state.m_region_model;
4244 bool call_discovered = false;
4246 if (tree fn_decl = model->get_fndecl_for_call (call, &ctxt))
4247 call_discovered = maybe_create_dynamic_call (call,
4254 if (!call_discovered)
4256 /* Check for jump through NULL. */
4257 if (tree fn_ptr = gimple_call_fn (call))
4259 const svalue *fn_ptr_sval
4260 = model->get_rvalue (fn_ptr, &ctxt);
4261 if (fn_ptr_sval->all_zeroes_p ())
4262 ctxt.warn (make_unique<jump_through_null> (call));
4265 /* An unknown function or a special function was called
4266 at this point, in such case, don't terminate the
4267 analysis of the current function.
4269 The analyzer handles calls to such functions while
4270 analysing the stmt itself, so the function call
4271 must have been handled by the anlyzer till now. */
4273 = get_or_create_node (next_point,
4277 add_edge (node, next, succ);
4281 if (!node->on_edge (*this, succ, &next_point, &next_state,
4285 logger->log ("skipping impossible edge to SN: %i",
4286 succ->m_dest->m_index);
4289 exploded_node *next = get_or_create_node (next_point, next_state,
4293 add_edge (node, next, succ);
4295 /* We might have a function entrypoint. */
4296 detect_infinite_recursion (next);
4300 /* Return from the calls which doesn't have a return superedge.
4301 Such case occurs when GCC's middle end didn't knew which function to
4302 call but analyzer did. */
4303 if ((is_an_exit_block && !found_a_superedge)
4304 && (!point.get_call_string ().empty_p ()))
4306 const call_string &cs = point.get_call_string ();
4307 program_point next_point
4308 = program_point::before_supernode (cs.get_caller_node (),
4311 program_state next_state (state);
4312 uncertainty_t uncertainty;
4315 = next_point.get_supernode ()->get_returning_call ();
4318 next_state.returning_call (*this, node, call, &uncertainty);
4320 if (next_state.m_valid)
4322 next_point.pop_from_call_stack ();
4323 exploded_node *enode = get_or_create_node (next_point,
4327 add_edge (node, enode, NULL,
4328 make_unique<dynamic_call_info_t> (call, true));
4336 /* Ensure that this graph has a stats instance for FN, return it.
4337 FN can be NULL, in which case a stats instances is returned covering
4338 "functionless" parts of the graph (the origin node). */
4341 exploded_graph::get_or_create_function_stats (function *fn)
4344 return &m_functionless_stats;
4346 if (stats **slot = m_per_function_stats.get (fn))
4350 int num_supernodes = fn ? n_basic_blocks_for_fn (fn) : 0;
4351 /* not quite the num supernodes, but nearly. */
4352 stats *new_stats = new stats (num_supernodes);
4353 m_per_function_stats.put (fn, new_stats);
4358 /* Print bar charts to PP showing:
4359 - the number of enodes per function, and
4360 - for each function:
4361 - the number of enodes per supernode/BB
4362 - the number of excess enodes per supernode/BB beyond the
4363 per-program-point limit, if there were any. */
4366 exploded_graph::print_bar_charts (pretty_printer *pp) const
4368 cgraph_node *cgnode;
4370 pp_string (pp, "enodes per function:");
4372 bar_chart enodes_per_function;
4373 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode)
4375 function *fn = cgnode->get_fun ();
4376 const stats * const *s_ptr
4377 = const_cast <function_stat_map_t &> (m_per_function_stats).get (fn);
4378 enodes_per_function.add_item (function_name (fn),
4379 s_ptr ? (*s_ptr)->get_total_enodes () : 0);
4381 enodes_per_function.print (pp);
4383 /* Accumulate number of enodes per supernode. */
4384 auto_vec<unsigned> enodes_per_supernode (m_sg.num_nodes ());
4385 for (int i = 0; i < m_sg.num_nodes (); i++)
4386 enodes_per_supernode.quick_push (0);
4388 exploded_node *enode;
4389 FOR_EACH_VEC_ELT (m_nodes, i, enode)
4391 const supernode *iter_snode = enode->get_supernode ();
4394 enodes_per_supernode[iter_snode->m_index]++;
4397 /* Accumulate excess enodes per supernode. */
4398 auto_vec<unsigned> excess_enodes_per_supernode (m_sg.num_nodes ());
4399 for (int i = 0; i < m_sg.num_nodes (); i++)
4400 excess_enodes_per_supernode.quick_push (0);
4401 for (point_map_t::iterator iter = m_per_point_data.begin ();
4402 iter != m_per_point_data.end (); ++iter)
4404 const program_point *point = (*iter).first;
4405 const supernode *iter_snode = point->get_supernode ();
4408 const per_program_point_data *point_data = (*iter).second;
4409 excess_enodes_per_supernode[iter_snode->m_index]
4410 += point_data->m_excess_enodes;
4413 /* Show per-function bar_charts of enodes per supernode/BB. */
4414 pp_string (pp, "per-function enodes per supernode/BB:");
4416 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode)
4418 function *fn = cgnode->get_fun ();
4419 pp_printf (pp, "function: %qs", function_name (fn));
4422 bar_chart enodes_per_snode;
4423 bar_chart excess_enodes_per_snode;
4424 bool have_excess_enodes = false;
4425 for (int i = 0; i < m_sg.num_nodes (); i++)
4427 const supernode *iter_snode = m_sg.get_node_by_index (i);
4428 if (iter_snode->get_function () != fn)
4430 pretty_printer tmp_pp;
4431 pp_printf (&tmp_pp, "sn %i (bb %i)",
4432 iter_snode->m_index, iter_snode->m_bb->index);
4433 enodes_per_snode.add_item (pp_formatted_text (&tmp_pp),
4434 enodes_per_supernode[iter_snode->m_index]);
4435 const int num_excess
4436 = excess_enodes_per_supernode[iter_snode->m_index];
4437 excess_enodes_per_snode.add_item (pp_formatted_text (&tmp_pp),
4440 have_excess_enodes = true;
4442 enodes_per_snode.print (pp);
4443 if (have_excess_enodes)
4445 pp_printf (pp, "EXCESS ENODES:");
4447 excess_enodes_per_snode.print (pp);
4452 /* Write all stats information to this graph's logger, if any. */
4455 exploded_graph::log_stats () const
4457 logger * const logger = get_logger ();
4463 m_ext_state.get_engine ()->log_stats (logger);
4465 logger->log ("m_sg.num_nodes (): %i", m_sg.num_nodes ());
4466 logger->log ("m_nodes.length (): %i", m_nodes.length ());
4467 logger->log ("m_edges.length (): %i", m_edges.length ());
4468 logger->log ("remaining enodes in worklist: %i", m_worklist.length ());
4470 logger->log ("global stats:");
4471 m_global_stats.log (logger);
4473 for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
4474 iter != m_per_function_stats.end ();
4477 function *fn = (*iter).first;
4478 log_scope s (logger, function_name (fn));
4479 (*iter).second->log (logger);
4482 print_bar_charts (logger->get_printer ());
4485 /* Dump all stats information to OUT. */
4488 exploded_graph::dump_stats (FILE *out) const
4490 fprintf (out, "m_sg.num_nodes (): %i\n", m_sg.num_nodes ());
4491 fprintf (out, "m_nodes.length (): %i\n", m_nodes.length ());
4492 fprintf (out, "m_edges.length (): %i\n", m_edges.length ());
4493 fprintf (out, "remaining enodes in worklist: %i", m_worklist.length ());
4495 fprintf (out, "global stats:\n");
4496 m_global_stats.dump (out);
4498 for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
4499 iter != m_per_function_stats.end ();
4502 function *fn = (*iter).first;
4503 fprintf (out, "function: %s\n", function_name (fn));
4504 (*iter).second->dump (out);
4507 fprintf (out, "PK_AFTER_SUPERNODE per supernode:\n");
4508 for (unsigned i = 0; i < m_PK_AFTER_SUPERNODE_per_snode.length (); i++)
4509 fprintf (out, " SN %i: %3i\n", i, m_PK_AFTER_SUPERNODE_per_snode[i]);
4513 exploded_graph::dump_states_for_supernode (FILE *out,
4514 const supernode *snode) const
4516 fprintf (out, "PK_AFTER_SUPERNODE nodes for SN: %i\n", snode->m_index);
4518 exploded_node *enode;
4520 FOR_EACH_VEC_ELT (m_nodes, i, enode)
4522 const supernode *iter_snode = enode->get_supernode ();
4523 if (enode->get_point ().get_kind () == PK_AFTER_SUPERNODE
4524 && iter_snode == snode)
4527 pp_format_decoder (&pp) = default_tree_printer;
4528 enode->get_state ().dump_to_pp (m_ext_state, true, false, &pp);
4529 fprintf (out, "state %i: EN: %i\n %s\n",
4530 state_idx++, enode->m_index,
4531 pp_formatted_text (&pp));
4534 fprintf (out, "#exploded_node for PK_AFTER_SUPERNODE for SN: %i = %i\n",
4535 snode->m_index, state_idx);
4538 /* Return a new json::object of the form
4539 {"nodes" : [objs for enodes],
4540 "edges" : [objs for eedges],
4541 "ext_state": object for extrinsic_state,
4542 "diagnostic_manager": object for diagnostic_manager}. */
4545 exploded_graph::to_json () const
4547 json::object *egraph_obj = new json::object ();
4551 json::array *nodes_arr = new json::array ();
4554 FOR_EACH_VEC_ELT (m_nodes, i, n)
4555 nodes_arr->append (n->to_json (m_ext_state));
4556 egraph_obj->set ("nodes", nodes_arr);
4561 json::array *edges_arr = new json::array ();
4564 FOR_EACH_VEC_ELT (m_edges, i, n)
4565 edges_arr->append (n->to_json ());
4566 egraph_obj->set ("edges", edges_arr);
4569 /* m_sg is JSONified at the top-level. */
4571 egraph_obj->set ("ext_state", m_ext_state.to_json ());
4572 egraph_obj->set ("worklist", m_worklist.to_json ());
4573 egraph_obj->set ("diagnostic_manager", m_diagnostic_manager.to_json ());
4575 /* The following fields aren't yet being JSONified:
4576 const state_purge_map *const m_purge_map;
4577 const analysis_plan &m_plan;
4578 stats m_global_stats;
4579 function_stat_map_t m_per_function_stats;
4580 stats m_functionless_stats;
4581 call_string_data_map_t m_per_call_string_data;
4582 auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode; */
4587 /* class exploded_path. */
4591 exploded_path::exploded_path (const exploded_path &other)
4592 : m_edges (other.m_edges.length ())
4595 const exploded_edge *eedge;
4596 FOR_EACH_VEC_ELT (other.m_edges, i, eedge)
4597 m_edges.quick_push (eedge);
4600 /* Look for the last use of SEARCH_STMT within this path.
4601 If found write the edge's index to *OUT_IDX and return true, otherwise
4605 exploded_path::find_stmt_backwards (const gimple *search_stmt,
4609 const exploded_edge *eedge;
4610 FOR_EACH_VEC_ELT_REVERSE (m_edges, i, eedge)
4612 const exploded_node *dst_node = eedge->m_dest;
4613 const program_point &dst_point = dst_node->get_point ();
4614 const gimple *stmt = dst_point.get_stmt ();
4615 if (stmt == search_stmt)
4624 /* Get the final exploded_node in this path, which must be non-empty. */
4627 exploded_path::get_final_enode () const
4629 gcc_assert (m_edges.length () > 0);
4630 return m_edges[m_edges.length () - 1]->m_dest;
4633 /* Check state along this path, returning true if it is feasible.
4634 If OUT is non-NULL, and the path is infeasible, write a new
4635 feasibility_problem to *OUT. */
4638 exploded_path::feasible_p (logger *logger,
4639 std::unique_ptr<feasibility_problem> *out,
4640 engine *eng, const exploded_graph *eg) const
4644 feasibility_state state (eng->get_model_manager (),
4645 eg->get_supergraph ());
4647 /* Traverse the path, updating this state. */
4648 for (unsigned edge_idx = 0; edge_idx < m_edges.length (); edge_idx++)
4650 const exploded_edge *eedge = m_edges[edge_idx];
4652 logger->log ("considering edge %i: EN:%i -> EN:%i",
4654 eedge->m_src->m_index,
4655 eedge->m_dest->m_index);
4657 rejected_constraint *rc = NULL;
4658 if (!state.maybe_update_for_edge (logger, eedge, &rc))
4663 const exploded_node &src_enode = *eedge->m_src;
4664 const program_point &src_point = src_enode.get_point ();
4665 const gimple *last_stmt
4666 = src_point.get_supernode ()->get_last_stmt ();
4667 *out = make_unique<feasibility_problem> (edge_idx, *eedge,
4677 logger->log ("state after edge %i: EN:%i -> EN:%i",
4679 eedge->m_src->m_index,
4680 eedge->m_dest->m_index);
4681 logger->start_log_line ();
4682 state.get_model ().dump_to_pp (logger->get_printer (), true, false);
4683 logger->end_log_line ();
4690 /* Dump this path in multiline form to PP.
4691 If EXT_STATE is non-NULL, then show the nodes. */
4694 exploded_path::dump_to_pp (pretty_printer *pp,
4695 const extrinsic_state *ext_state) const
4697 for (unsigned i = 0; i < m_edges.length (); i++)
4699 const exploded_edge *eedge = m_edges[i];
4700 pp_printf (pp, "m_edges[%i]: EN %i -> EN %i",
4702 eedge->m_src->m_index,
4703 eedge->m_dest->m_index);
4707 eedge->m_dest->dump_to_pp (pp, *ext_state);
4711 /* Dump this path in multiline form to FP. */
4714 exploded_path::dump (FILE *fp, const extrinsic_state *ext_state) const
4717 pp_format_decoder (&pp) = default_tree_printer;
4718 pp_show_color (&pp) = pp_show_color (global_dc->printer);
4719 pp.buffer->stream = fp;
4720 dump_to_pp (&pp, ext_state);
4724 /* Dump this path in multiline form to stderr. */
4727 exploded_path::dump (const extrinsic_state *ext_state) const
4729 dump (stderr, ext_state);
4732 /* Dump this path verbosely to FILENAME. */
4735 exploded_path::dump_to_file (const char *filename,
4736 const extrinsic_state &ext_state) const
4738 FILE *fp = fopen (filename, "w");
4742 pp_format_decoder (&pp) = default_tree_printer;
4743 pp.buffer->stream = fp;
4744 dump_to_pp (&pp, &ext_state);
4749 /* class feasibility_problem. */
4752 feasibility_problem::dump_to_pp (pretty_printer *pp) const
4754 pp_printf (pp, "edge from EN: %i to EN: %i",
4755 m_eedge.m_src->m_index, m_eedge.m_dest->m_index);
4758 pp_string (pp, "; rejected constraint: ");
4759 m_rc->dump_to_pp (pp);
4760 pp_string (pp, "; rmodel: ");
4761 m_rc->get_model ().dump_to_pp (pp, true, false);
4765 /* class feasibility_state. */
4767 /* Ctor for feasibility_state, at the beginning of a path. */
4769 feasibility_state::feasibility_state (region_model_manager *manager,
4770 const supergraph &sg)
4771 : m_model (manager),
4772 m_snodes_visited (sg.m_nodes.length ())
4774 bitmap_clear (m_snodes_visited);
4777 /* Copy ctor for feasibility_state, for extending a path. */
4779 feasibility_state::feasibility_state (const feasibility_state &other)
4780 : m_model (other.m_model),
4781 m_snodes_visited (const_sbitmap (other.m_snodes_visited)->n_bits)
4783 bitmap_copy (m_snodes_visited, other.m_snodes_visited);
4786 /* The heart of feasibility-checking.
4788 Attempt to update this state in-place based on traversing EEDGE
4790 Update the model for the stmts in the src enode.
4791 Attempt to add constraints for EEDGE.
4793 If feasible, return true.
4794 Otherwise, return false and write to *OUT_RC. */
4797 feasibility_state::maybe_update_for_edge (logger *logger,
4798 const exploded_edge *eedge,
4799 rejected_constraint **out_rc)
4801 const exploded_node &src_enode = *eedge->m_src;
4802 const program_point &src_point = src_enode.get_point ();
4805 logger->start_log_line ();
4806 src_point.print (logger->get_printer (), format (false));
4807 logger->end_log_line ();
4810 /* Update state for the stmts that were processed in each enode. */
4811 for (unsigned stmt_idx = 0; stmt_idx < src_enode.m_num_processed_stmts;
4814 const gimple *stmt = src_enode.get_processed_stmt (stmt_idx);
4816 /* Update cfun and input_location in case of ICE: make it easier to
4817 track down which source construct we're failing to handle. */
4818 auto_cfun sentinel (src_point.get_function ());
4819 input_location = stmt->location;
4821 if (const gassign *assign = dyn_cast <const gassign *> (stmt))
4822 m_model.on_assignment (assign, NULL);
4823 else if (const gasm *asm_stmt = dyn_cast <const gasm *> (stmt))
4824 m_model.on_asm_stmt (asm_stmt, NULL);
4825 else if (const gcall *call = dyn_cast <const gcall *> (stmt))
4827 bool unknown_side_effects = m_model.on_call_pre (call, NULL);
4828 m_model.on_call_post (call, unknown_side_effects, NULL);
4830 else if (const greturn *return_ = dyn_cast <const greturn *> (stmt))
4831 m_model.on_return (return_, NULL);
4834 const superedge *sedge = eedge->m_sedge;
4839 label_text desc (sedge->get_description (false));
4840 logger->log (" sedge: SN:%i -> SN:%i %s",
4841 sedge->m_src->m_index,
4842 sedge->m_dest->m_index,
4846 const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt ();
4847 if (!m_model.maybe_update_for_edge (*sedge, last_stmt, NULL, out_rc))
4851 logger->log ("rejecting due to region model");
4852 m_model.dump_to_pp (logger->get_printer (), true, false);
4859 /* Special-case the initial eedge from the origin node to the
4860 initial function by pushing a frame for it. */
4861 if (src_point.get_kind () == PK_ORIGIN)
4863 gcc_assert (eedge->m_src->m_index == 0);
4864 gcc_assert (eedge->m_dest->get_point ().get_kind ()
4865 == PK_BEFORE_SUPERNODE);
4866 function *fun = eedge->m_dest->get_function ();
4868 m_model.push_frame (fun, NULL, NULL);
4870 logger->log (" pushing frame for %qD", fun->decl);
4872 else if (eedge->m_custom_info)
4874 eedge->m_custom_info->update_model (&m_model, eedge, NULL);
4878 /* Handle phi nodes on an edge leaving a PK_BEFORE_SUPERNODE (to
4879 a PK_BEFORE_STMT, or a PK_AFTER_SUPERNODE if no stmts).
4880 This will typically not be associated with a superedge. */
4881 if (src_point.get_from_edge ())
4883 const cfg_superedge *last_cfg_superedge
4884 = src_point.get_from_edge ()->dyn_cast_cfg_superedge ();
4885 const exploded_node &dst_enode = *eedge->m_dest;
4886 const unsigned dst_snode_idx = dst_enode.get_supernode ()->m_index;
4887 if (last_cfg_superedge)
4890 logger->log (" update for phis");
4891 m_model.update_for_phis (src_enode.get_supernode (),
4894 /* If we've entering an snode that we've already visited on this
4895 epath, then we need do fix things up for loops; see the
4896 comment for store::loop_replay_fixup.
4897 Perhaps we should probably also verify the callstring,
4898 and track program_points, but hopefully doing it by supernode
4900 if (bitmap_bit_p (m_snodes_visited, dst_snode_idx))
4901 m_model.loop_replay_fixup (dst_enode.get_state ().m_region_model);
4903 bitmap_set_bit (m_snodes_visited, dst_snode_idx);
4908 /* Dump this object to PP. */
4911 feasibility_state::dump_to_pp (pretty_printer *pp,
4912 bool simple, bool multiline) const
4914 m_model.dump_to_pp (pp, simple, multiline);
4917 /* A family of cluster subclasses for use when generating .dot output for
4918 exploded graphs (-fdump-analyzer-exploded-graph), for grouping the
4919 enodes into hierarchical boxes.
4921 All functionless enodes appear in the top-level graph.
4922 Every (function, call_string) pair gets its own cluster. Within that
4923 cluster, each supernode gets its own cluster.
4925 Hence all enodes relating to a particular function with a particular
4926 callstring will be in a cluster together; all enodes for the same
4927 function but with a different callstring will be in a different
4930 /* Base class of cluster for clustering exploded_node instances in .dot
4931 output, based on various subclass-specific criteria. */
4933 class exploded_cluster : public cluster<eg_traits>
4937 /* Cluster containing all exploded_node instances for one supernode. */
4939 class supernode_cluster : public exploded_cluster
4942 supernode_cluster (const supernode *supernode) : m_supernode (supernode) {}
4946 void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
4948 gv->println ("subgraph \"cluster_supernode_%i\" {", m_supernode->m_index);
4950 gv->println ("style=\"dashed\";");
4951 gv->println ("label=\"SN: %i (bb: %i; scc: %i)\";",
4952 m_supernode->m_index, m_supernode->m_bb->index,
4953 args.m_eg.get_scc_id (*m_supernode));
4956 exploded_node *enode;
4957 FOR_EACH_VEC_ELT (m_enodes, i, enode)
4958 enode->dump_dot (gv, args);
4960 /* Terminate subgraph. */
4965 void add_node (exploded_node *en) final override
4967 m_enodes.safe_push (en);
4970 /* Comparator for use by auto_vec<supernode_cluster *>::qsort. */
4972 static int cmp_ptr_ptr (const void *p1, const void *p2)
4974 const supernode_cluster *c1
4975 = *(const supernode_cluster * const *)p1;
4976 const supernode_cluster *c2
4977 = *(const supernode_cluster * const *)p2;
4978 return c1->m_supernode->m_index - c2->m_supernode->m_index;
4982 const supernode *m_supernode;
4983 auto_vec <exploded_node *> m_enodes;
4986 /* Cluster containing all supernode_cluster instances for one
4987 (function, call_string) pair. */
4989 class function_call_string_cluster : public exploded_cluster
4992 function_call_string_cluster (function *fun, const call_string &cs)
4993 : m_fun (fun), m_cs (cs) {}
4995 ~function_call_string_cluster ()
4997 for (map_t::iterator iter = m_map.begin ();
4998 iter != m_map.end ();
5000 delete (*iter).second;
5003 void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
5005 const char *funcname = function_name (m_fun);
5007 gv->println ("subgraph \"cluster_function_%s\" {",
5008 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (m_fun->decl)));
5010 gv->write_indent ();
5011 gv->print ("label=\"call string: ");
5012 m_cs.print (gv->get_pp ());
5013 gv->print (" function: %s \";", funcname);
5016 /* Dump m_map, sorting it to avoid churn when comparing dumps. */
5017 auto_vec<supernode_cluster *> child_clusters (m_map.elements ());
5018 for (map_t::iterator iter = m_map.begin ();
5019 iter != m_map.end ();
5021 child_clusters.quick_push ((*iter).second);
5023 child_clusters.qsort (supernode_cluster::cmp_ptr_ptr);
5026 supernode_cluster *child_cluster;
5027 FOR_EACH_VEC_ELT (child_clusters, i, child_cluster)
5028 child_cluster->dump_dot (gv, args);
5030 /* Terminate subgraph. */
5035 void add_node (exploded_node *en) final override
5037 const supernode *supernode = en->get_supernode ();
5038 gcc_assert (supernode);
5039 supernode_cluster **slot = m_map.get (supernode);
5041 (*slot)->add_node (en);
5044 supernode_cluster *child = new supernode_cluster (supernode);
5045 m_map.put (supernode, child);
5046 child->add_node (en);
5050 /* Comparator for use by auto_vec<function_call_string_cluster *>. */
5052 static int cmp_ptr_ptr (const void *p1, const void *p2)
5054 const function_call_string_cluster *c1
5055 = *(const function_call_string_cluster * const *)p1;
5056 const function_call_string_cluster *c2
5057 = *(const function_call_string_cluster * const *)p2;
5059 = strcmp (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c1->m_fun->decl)),
5060 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c2->m_fun->decl))))
5062 return call_string::cmp (c1->m_cs, c2->m_cs);
5067 const call_string &m_cs;
5068 typedef ordered_hash_map<const supernode *, supernode_cluster *> map_t;
5072 /* Keys for root_cluster. */
5074 struct function_call_string
5076 function_call_string (function *fun, const call_string *cs)
5077 : m_fun (fun), m_cs (cs)
5084 const call_string *m_cs;
5089 template <> struct default_hash_traits<function_call_string>
5090 : public pod_hash_traits<function_call_string>
5092 static const bool empty_zero_p = false;
5097 pod_hash_traits<function_call_string>::hash (value_type v)
5099 return (pointer_hash <function>::hash (v.m_fun)
5100 ^ pointer_hash <const call_string>::hash (v.m_cs));
5105 pod_hash_traits<function_call_string>::equal (const value_type &existing,
5106 const value_type &candidate)
5108 return existing.m_fun == candidate.m_fun && &existing.m_cs == &candidate.m_cs;
5112 pod_hash_traits<function_call_string>::mark_deleted (value_type &v)
5114 v.m_fun = reinterpret_cast<function *> (1);
5118 pod_hash_traits<function_call_string>::mark_empty (value_type &v)
5124 pod_hash_traits<function_call_string>::is_deleted (value_type v)
5126 return v.m_fun == reinterpret_cast<function *> (1);
5130 pod_hash_traits<function_call_string>::is_empty (value_type v)
5132 return v.m_fun == NULL;
5137 /* Top-level cluster for generating .dot output for exploded graphs,
5138 handling the functionless nodes, and grouping the remaining nodes by
5141 class root_cluster : public exploded_cluster
5146 for (map_t::iterator iter = m_map.begin ();
5147 iter != m_map.end ();
5149 delete (*iter).second;
5152 void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
5155 exploded_node *enode;
5156 FOR_EACH_VEC_ELT (m_functionless_enodes, i, enode)
5157 enode->dump_dot (gv, args);
5159 /* Dump m_map, sorting it to avoid churn when comparing dumps. */
5160 auto_vec<function_call_string_cluster *> child_clusters (m_map.elements ());
5161 for (map_t::iterator iter = m_map.begin ();
5162 iter != m_map.end ();
5164 child_clusters.quick_push ((*iter).second);
5166 child_clusters.qsort (function_call_string_cluster::cmp_ptr_ptr);
5168 function_call_string_cluster *child_cluster;
5169 FOR_EACH_VEC_ELT (child_clusters, i, child_cluster)
5170 child_cluster->dump_dot (gv, args);
5173 void add_node (exploded_node *en) final override
5175 function *fun = en->get_function ();
5178 m_functionless_enodes.safe_push (en);
5182 const call_string &cs = en->get_point ().get_call_string ();
5183 function_call_string key (fun, &cs);
5184 function_call_string_cluster **slot = m_map.get (key);
5186 (*slot)->add_node (en);
5189 function_call_string_cluster *child
5190 = new function_call_string_cluster (fun, cs);
5191 m_map.put (key, child);
5192 child->add_node (en);
5197 typedef hash_map<function_call_string, function_call_string_cluster *> map_t;
5200 /* This should just be the origin exploded_node. */
5201 auto_vec <exploded_node *> m_functionless_enodes;
5204 /* Subclass of range_label for use within
5205 exploded_graph::dump_exploded_nodes for implementing
5206 -fdump-analyzer-exploded-nodes: a label for a specific
5209 class enode_label : public range_label
5212 enode_label (const extrinsic_state &ext_state,
5213 exploded_node *enode)
5214 : m_ext_state (ext_state), m_enode (enode) {}
5216 label_text get_text (unsigned) const final override
5219 pp_format_decoder (&pp) = default_tree_printer;
5220 m_enode->get_state ().dump_to_pp (m_ext_state, true, false, &pp);
5221 return make_label_text (false, "EN: %i: %s",
5222 m_enode->m_index, pp_formatted_text (&pp));
5226 const extrinsic_state &m_ext_state;
5227 exploded_node *m_enode;
5230 /* Postprocessing support for dumping the exploded nodes.
5231 Handle -fdump-analyzer-exploded-nodes,
5232 -fdump-analyzer-exploded-nodes-2, and the
5233 "__analyzer_dump_exploded_nodes" builtin. */
5236 exploded_graph::dump_exploded_nodes () const
5239 /* Locate calls to __analyzer_dump_exploded_nodes. */
5240 // Print how many egs there are for them?
5241 /* Better: log them as we go, and record the exploded nodes
5244 /* Show every enode. */
5246 /* Gather them by stmt, so that we can more clearly see the
5247 "hotspots" requiring numerous exploded nodes. */
5249 /* Alternatively, simply throw them all into one big rich_location
5250 and see if the label-printing will sort it out...
5251 This requires them all to be in the same source file. */
5253 if (flag_dump_analyzer_exploded_nodes)
5255 auto_timevar tv (TV_ANALYZER_DUMP);
5256 gcc_rich_location richloc (UNKNOWN_LOCATION);
5258 exploded_node *enode;
5259 FOR_EACH_VEC_ELT (m_nodes, i, enode)
5261 if (const gimple *stmt = enode->get_stmt ())
5263 if (get_pure_location (richloc.get_loc ()) == UNKNOWN_LOCATION)
5264 richloc.set_range (0, stmt->location, SHOW_RANGE_WITH_CARET);
5266 richloc.add_range (stmt->location,
5267 SHOW_RANGE_WITHOUT_CARET,
5268 new enode_label (m_ext_state, enode));
5271 warning_at (&richloc, 0, "%i exploded nodes", m_nodes.length ());
5273 /* Repeat the warning without all the labels, so that message is visible
5274 (the other one may well have scrolled past the terminal limit). */
5275 warning_at (richloc.get_loc (), 0,
5276 "%i exploded nodes", m_nodes.length ());
5278 if (m_worklist.length () > 0)
5279 warning_at (richloc.get_loc (), 0,
5280 "worklist still contains %i nodes", m_worklist.length ());
5283 /* Dump the egraph in textual form to a dump file. */
5284 if (flag_dump_analyzer_exploded_nodes_2)
5286 auto_timevar tv (TV_ANALYZER_DUMP);
5288 = concat (dump_base_name, ".eg.txt", NULL);
5289 FILE *outf = fopen (filename, "w");
5291 error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
5294 fprintf (outf, "exploded graph for %s\n", dump_base_name);
5295 fprintf (outf, " nodes: %i\n", m_nodes.length ());
5296 fprintf (outf, " edges: %i\n", m_edges.length ());
5299 exploded_node *enode;
5300 FOR_EACH_VEC_ELT (m_nodes, i, enode)
5302 fprintf (outf, "\nEN %i:\n", enode->m_index);
5303 enode->dump_succs_and_preds (outf);
5305 enode->get_point ().print (&pp, format (true));
5306 fprintf (outf, "%s\n", pp_formatted_text (&pp));
5307 enode->get_state ().dump_to_file (m_ext_state, false, true, outf);
5313 /* Dump the egraph in textual form to multiple dump files, one per enode. */
5314 if (flag_dump_analyzer_exploded_nodes_3)
5316 auto_timevar tv (TV_ANALYZER_DUMP);
5319 exploded_node *enode;
5320 FOR_EACH_VEC_ELT (m_nodes, i, enode)
5323 = xasprintf ("%s.en-%i.txt", dump_base_name, i);
5324 FILE *outf = fopen (filename, "w");
5326 error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
5329 fprintf (outf, "EN %i:\n", enode->m_index);
5330 enode->dump_succs_and_preds (outf);
5332 enode->get_point ().print (&pp, format (true));
5333 fprintf (outf, "%s\n", pp_formatted_text (&pp));
5334 enode->get_state ().dump_to_file (m_ext_state, false, true, outf);
5340 /* Emit a warning at any call to "__analyzer_dump_exploded_nodes",
5341 giving the number of processed exploded nodes for "before-stmt",
5342 and the IDs of processed, merger, and worklist enodes.
5344 We highlight the count of *processed* enodes since this is of most
5345 interest in DejaGnu tests for ensuring that state merger has
5348 We don't show the count of merger and worklist enodes, as this is
5349 more of an implementation detail of the merging/worklist that we
5350 don't want to bake into our expected DejaGnu messages. */
5353 exploded_node *enode;
5354 hash_set<const gimple *> seen;
5355 FOR_EACH_VEC_ELT (m_nodes, i, enode)
5357 if (enode->get_point ().get_kind () != PK_BEFORE_STMT)
5360 if (const gimple *stmt = enode->get_stmt ())
5361 if (const gcall *call = dyn_cast <const gcall *> (stmt))
5362 if (is_special_named_call_p (call, "__analyzer_dump_exploded_nodes",
5365 if (seen.contains (stmt))
5368 auto_vec<exploded_node *> processed_enodes;
5369 auto_vec<exploded_node *> merger_enodes;
5370 auto_vec<exploded_node *> worklist_enodes;
5371 /* This is O(N^2). */
5373 exploded_node *other_enode;
5374 FOR_EACH_VEC_ELT (m_nodes, j, other_enode)
5376 if (other_enode->get_point ().get_kind () != PK_BEFORE_STMT)
5378 if (other_enode->get_stmt () == stmt)
5379 switch (other_enode->get_status ())
5383 case exploded_node::STATUS_WORKLIST:
5384 worklist_enodes.safe_push (other_enode);
5386 case exploded_node::STATUS_PROCESSED:
5387 processed_enodes.safe_push (other_enode);
5389 case exploded_node::STATUS_MERGER:
5390 merger_enodes.safe_push (other_enode);
5396 pp_character (&pp, '[');
5397 print_enode_indices (&pp, processed_enodes);
5398 if (merger_enodes.length () > 0)
5400 pp_string (&pp, "] merger(s): [");
5401 print_enode_indices (&pp, merger_enodes);
5403 if (worklist_enodes.length () > 0)
5405 pp_string (&pp, "] worklist: [");
5406 print_enode_indices (&pp, worklist_enodes);
5408 pp_character (&pp, ']');
5410 warning_n (stmt->location, 0, processed_enodes.length (),
5411 "%i processed enode: %s",
5412 "%i processed enodes: %s",
5413 processed_enodes.length (), pp_formatted_text (&pp));
5416 /* If the argument is non-zero, then print all of the states
5417 of the various enodes. */
5418 tree t_arg = fold (gimple_call_arg (call, 0));
5419 if (TREE_CODE (t_arg) != INTEGER_CST)
5421 error_at (call->location,
5422 "integer constant required for arg 1");
5425 int i_arg = TREE_INT_CST_LOW (t_arg);
5428 exploded_node *other_enode;
5429 FOR_EACH_VEC_ELT (processed_enodes, j, other_enode)
5431 fprintf (stderr, "%i of %i: EN %i:\n",
5432 j + 1, processed_enodes.length (),
5433 other_enode->m_index);
5434 other_enode->dump_succs_and_preds (stderr);
5436 other_enode->get_state ().dump (m_ext_state, false);
5443 DEBUG_FUNCTION exploded_node *
5444 exploded_graph::get_node_by_index (int idx) const
5446 exploded_node *enode = m_nodes[idx];
5447 gcc_assert (enode->m_index == idx);
5451 /* Ensure that there is an exploded_node for a top-level call to FNDECL. */
5454 exploded_graph::on_escaped_function (tree fndecl)
5456 logger * const logger = get_logger ();
5457 LOG_FUNC_1 (logger, "%qE", fndecl);
5459 cgraph_node *cgnode = cgraph_node::get (fndecl);
5463 function *fun = cgnode->get_fun ();
5467 if (!gimple_has_body_p (fndecl))
5470 exploded_node *enode = add_function_entry (fun);
5474 logger->log ("created EN %i for %qE entrypoint",
5475 enode->m_index, fun->decl);
5477 logger->log ("did not create enode for %qE entrypoint", fun->decl);
5481 /* A collection of classes for visualizing the callgraph in .dot form
5482 (as represented in the supergraph). */
5484 /* Forward decls. */
5485 class viz_callgraph_node;
5486 class viz_callgraph_edge;
5487 class viz_callgraph;
5488 class viz_callgraph_cluster;
5490 /* Traits for using "digraph.h" to visualize the callgraph. */
5492 struct viz_callgraph_traits
5494 typedef viz_callgraph_node node_t;
5495 typedef viz_callgraph_edge edge_t;
5496 typedef viz_callgraph graph_t;
5499 dump_args_t (const exploded_graph *eg) : m_eg (eg) {}
5500 const exploded_graph *m_eg;
5502 typedef viz_callgraph_cluster cluster_t;
5505 /* Subclass of dnode representing a function within the callgraph. */
5507 class viz_callgraph_node : public dnode<viz_callgraph_traits>
5509 friend class viz_callgraph;
5512 viz_callgraph_node (function *fun, int index)
5513 : m_fun (fun), m_index (index), m_num_supernodes (0), m_num_superedges (0)
5518 void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
5520 pretty_printer *pp = gv->get_pp ();
5523 pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
5525 pp_write_text_to_stream (pp);
5527 pp_printf (pp, "VCG: %i: %s", m_index, function_name (m_fun));
5530 pp_printf (pp, "supernodes: %i\n", m_num_supernodes);
5533 pp_printf (pp, "superedges: %i\n", m_num_superedges);
5539 exploded_node *enode;
5540 unsigned num_enodes = 0;
5541 FOR_EACH_VEC_ELT (args.m_eg->m_nodes, i, enode)
5543 if (enode->get_point ().get_function () == m_fun)
5546 pp_printf (pp, "enodes: %i\n", num_enodes);
5549 // TODO: also show the per-callstring breakdown
5550 const exploded_graph::call_string_data_map_t *per_cs_data
5551 = args.m_eg->get_per_call_string_data ();
5552 for (exploded_graph::call_string_data_map_t::iterator iter
5553 = per_cs_data->begin ();
5554 iter != per_cs_data->end ();
5557 const call_string *cs = (*iter).first;
5558 //per_call_string_data *data = (*iter).second;
5560 FOR_EACH_VEC_ELT (args.m_eg->m_nodes, i, enode)
5562 if (enode->get_point ().get_function () == m_fun
5563 && &enode->get_point ().get_call_string () == cs)
5569 pp_printf (pp, ": %i\n", num_enodes);
5573 /* Show any summaries. */
5574 per_function_data *data = args.m_eg->get_per_function_data (m_fun);
5578 pp_printf (pp, "summaries: %i\n", data->m_summaries.length ());
5579 for (auto summary : data->m_summaries)
5581 pp_printf (pp, "\nsummary: %s:\n", summary->get_desc ().get ());
5582 const extrinsic_state &ext_state = args.m_eg->get_ext_state ();
5583 const program_state &state = summary->get_state ();
5584 state.dump_to_pp (ext_state, false, true, pp);
5590 pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
5591 pp_string (pp, "\"];\n\n");
5595 void dump_dot_id (pretty_printer *pp) const
5597 pp_printf (pp, "vcg_%i", m_index);
5603 int m_num_supernodes;
5604 int m_num_superedges;
5607 /* Subclass of dedge representing a callgraph edge. */
5609 class viz_callgraph_edge : public dedge<viz_callgraph_traits>
5612 viz_callgraph_edge (viz_callgraph_node *src, viz_callgraph_node *dest)
5613 : dedge<viz_callgraph_traits> (src, dest)
5616 void dump_dot (graphviz_out *gv, const dump_args_t &) const
5619 pretty_printer *pp = gv->get_pp ();
5621 const char *style = "\"solid,bold\"";
5622 const char *color = "black";
5624 const char *constraint = "true";
5626 m_src->dump_dot_id (pp);
5627 pp_string (pp, " -> ");
5628 m_dest->dump_dot_id (pp);
5630 (" [style=%s, color=%s, weight=%d, constraint=%s,"
5632 style, color, weight, constraint);
5633 pp_printf (pp, "\"];\n");
5637 /* Subclass of digraph representing the callgraph. */
5639 class viz_callgraph : public digraph<viz_callgraph_traits>
5642 viz_callgraph (const supergraph &sg);
5644 viz_callgraph_node *get_vcg_node_for_function (function *fun)
5646 return *m_map.get (fun);
5649 viz_callgraph_node *get_vcg_node_for_snode (supernode *snode)
5651 return get_vcg_node_for_function (snode->m_fun);
5655 hash_map<function *, viz_callgraph_node *> m_map;
5658 /* Placeholder subclass of cluster. */
5660 class viz_callgraph_cluster : public cluster<viz_callgraph_traits>
5664 /* viz_callgraph's ctor. */
5666 viz_callgraph::viz_callgraph (const supergraph &sg)
5669 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
5671 function *fun = node->get_fun ();
5672 viz_callgraph_node *vcg_node
5673 = new viz_callgraph_node (fun, m_nodes.length ());
5674 m_map.put (fun, vcg_node);
5675 add_node (vcg_node);
5680 FOR_EACH_VEC_ELT (sg.m_edges, i, sedge)
5682 viz_callgraph_node *vcg_src = get_vcg_node_for_snode (sedge->m_src);
5684 get_vcg_node_for_function (vcg_src->m_fun)->m_num_superedges++;
5685 if (sedge->dyn_cast_call_superedge ())
5687 viz_callgraph_node *vcg_dest = get_vcg_node_for_snode (sedge->m_dest);
5688 viz_callgraph_edge *vcg_edge
5689 = new viz_callgraph_edge (vcg_src, vcg_dest);
5690 add_edge (vcg_edge);
5695 FOR_EACH_VEC_ELT (sg.m_nodes, i, snode)
5698 get_vcg_node_for_function (snode->m_fun)->m_num_supernodes++;
5702 /* Dump the callgraph to FILENAME. */
5705 dump_callgraph (const supergraph &sg, const char *filename,
5706 const exploded_graph *eg)
5708 FILE *outf = fopen (filename, "w");
5713 viz_callgraph vcg (sg);
5714 vcg.dump_dot (filename, NULL, viz_callgraph_traits::dump_args_t (eg));
5719 /* Dump the callgraph to "<srcfile>.callgraph.dot". */
5722 dump_callgraph (const supergraph &sg, const exploded_graph *eg)
5724 auto_timevar tv (TV_ANALYZER_DUMP);
5725 char *filename = concat (dump_base_name, ".callgraph.dot", NULL);
5726 dump_callgraph (sg, filename, eg);
5730 /* Subclass of dot_annotator for implementing
5731 DUMP_BASE_NAME.supergraph-eg.dot, a post-analysis dump of the supergraph.
5733 Annotate the supergraph nodes by printing the exploded nodes in concise
5734 form within them, next to their pertinent statements where appropriate,
5735 colorizing the exploded nodes based on sm-state.
5736 Also show saved diagnostics within the exploded nodes, giving information
5737 on whether they were feasible, and, if infeasible, where the problem
5740 class exploded_graph_annotator : public dot_annotator
5743 exploded_graph_annotator (const exploded_graph &eg)
5746 /* Avoid O(N^2) by prepopulating m_enodes_per_snodes. */
5749 FOR_EACH_VEC_ELT (eg.get_supergraph ().m_nodes, i, snode)
5750 m_enodes_per_snodes.safe_push (new auto_vec <exploded_node *> ());
5751 exploded_node *enode;
5752 FOR_EACH_VEC_ELT (m_eg.m_nodes, i, enode)
5753 if (enode->get_supernode ())
5754 m_enodes_per_snodes[enode->get_supernode ()->m_index]->safe_push (enode);
5757 /* Show exploded nodes for BEFORE_SUPERNODE points before N. */
5758 bool add_node_annotations (graphviz_out *gv, const supernode &n,
5760 const final override
5765 pretty_printer *pp = gv->get_pp ();
5768 pp_string (pp, "BEFORE");
5769 pp_printf (pp, " (scc: %i)", m_eg.get_scc_id (n));
5773 exploded_node *enode;
5774 bool had_enode = false;
5775 FOR_EACH_VEC_ELT (*m_enodes_per_snodes[n.m_index], i, enode)
5777 gcc_assert (enode->get_supernode () == &n);
5778 const program_point &point = enode->get_point ();
5779 if (point.get_kind () != PK_BEFORE_SUPERNODE)
5781 print_enode (gv, enode);
5785 pp_string (pp, "<TD BGCOLOR=\"red\">UNREACHED</TD>");
5791 /* Show exploded nodes for STMT. */
5792 void add_stmt_annotations (graphviz_out *gv, const gimple *stmt,
5794 const final override
5798 pretty_printer *pp = gv->get_pp ();
5800 const supernode *snode
5801 = m_eg.get_supergraph ().get_supernode_for_stmt (stmt);
5803 exploded_node *enode;
5804 bool had_td = false;
5805 FOR_EACH_VEC_ELT (*m_enodes_per_snodes[snode->m_index], i, enode)
5807 const program_point &point = enode->get_point ();
5808 if (point.get_kind () != PK_BEFORE_STMT)
5810 if (point.get_stmt () != stmt)
5812 print_enode (gv, enode);
5823 /* Show exploded nodes for AFTER_SUPERNODE points after N. */
5824 bool add_after_node_annotations (graphviz_out *gv, const supernode &n)
5825 const final override
5828 pretty_printer *pp = gv->get_pp ();
5831 pp_string (pp, "AFTER");
5835 exploded_node *enode;
5836 FOR_EACH_VEC_ELT (*m_enodes_per_snodes[n.m_index], i, enode)
5838 gcc_assert (enode->get_supernode () == &n);
5839 const program_point &point = enode->get_point ();
5840 if (point.get_kind () != PK_AFTER_SUPERNODE)
5842 print_enode (gv, enode);
5850 /* Concisely print a TD element for ENODE, showing the index, status,
5851 and any saved_diagnostics at the enode. Colorize it to show sm-state.
5853 Ideally we'd dump ENODE's state here, hidden behind some kind of
5854 interactive disclosure method like a tooltip, so that the states
5855 can be explored without overwhelming the graph.
5856 However, I wasn't able to get graphviz/xdot to show tooltips on
5857 individual elements within a HTML-like label. */
5858 void print_enode (graphviz_out *gv, const exploded_node *enode) const
5860 pretty_printer *pp = gv->get_pp ();
5861 pp_printf (pp, "<TD BGCOLOR=\"%s\">",
5862 enode->get_dot_fillcolor ());
5863 pp_printf (pp, "<TABLE BORDER=\"0\">");
5865 pp_printf (pp, "EN: %i", enode->m_index);
5866 switch (enode->get_status ())
5870 case exploded_node::STATUS_WORKLIST:
5871 pp_string (pp, "(W)");
5873 case exploded_node::STATUS_PROCESSED:
5875 case exploded_node::STATUS_MERGER:
5876 pp_string (pp, "(M)");
5878 case exploded_node::STATUS_BULK_MERGED:
5879 pp_string (pp, "(BM)");
5884 /* Dump any saved_diagnostics at this enode. */
5885 for (unsigned i = 0; i < enode->get_num_diagnostics (); i++)
5887 const saved_diagnostic *sd = enode->get_saved_diagnostic (i);
5888 print_saved_diagnostic (gv, sd);
5890 pp_printf (pp, "</TABLE>");
5891 pp_printf (pp, "</TD>");
5894 /* Print a TABLE element for SD, showing the kind, the length of the
5895 exploded_path, whether the path was feasible, and if infeasible,
5896 what the problem was. */
5897 void print_saved_diagnostic (graphviz_out *gv,
5898 const saved_diagnostic *sd) const
5900 pretty_printer *pp = gv->get_pp ();
5902 pp_printf (pp, "<TABLE BORDER=\"0\">");
5904 pp_string (pp, "<TD BGCOLOR=\"green\">");
5905 pp_printf (pp, "DIAGNOSTIC: %s", sd->m_d->get_kind ());
5908 if (sd->get_best_epath ())
5909 pp_printf (pp, "epath length: %i", sd->get_epath_length ());
5911 pp_printf (pp, "no best epath");
5913 if (const feasibility_problem *p = sd->get_feasibility_problem ())
5916 pp_printf (pp, "INFEASIBLE at eedge %i: EN:%i -> EN:%i",
5918 p->m_eedge.m_src->m_index,
5919 p->m_eedge.m_dest->m_index);
5920 pp_write_text_as_html_like_dot_to_stream (pp);
5923 p->m_eedge.m_sedge->dump (pp);
5924 pp_write_text_as_html_like_dot_to_stream (pp);
5927 pp_gimple_stmt_1 (pp, p->m_last_stmt, 0, (dump_flags_t)0);
5928 pp_write_text_as_html_like_dot_to_stream (pp);
5930 /* Ideally we'd print p->m_model here; see the notes above about
5933 pp_printf (pp, "</TABLE>");
5937 const exploded_graph &m_eg;
5938 auto_delete_vec<auto_vec <exploded_node *> > m_enodes_per_snodes;
5941 /* Implement -fdump-analyzer-json. */
5944 dump_analyzer_json (const supergraph &sg,
5945 const exploded_graph &eg)
5947 auto_timevar tv (TV_ANALYZER_DUMP);
5948 char *filename = concat (dump_base_name, ".analyzer.json.gz", NULL);
5949 gzFile output = gzopen (filename, "w");
5952 error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
5957 json::object *toplev_obj = new json::object ();
5958 toplev_obj->set ("sgraph", sg.to_json ());
5959 toplev_obj->set ("egraph", eg.to_json ());
5962 toplev_obj->print (&pp);
5963 pp_formatted_text (&pp);
5967 if (gzputs (output, pp_formatted_text (&pp)) == EOF
5968 || gzclose (output))
5969 error_at (UNKNOWN_LOCATION, "error writing %qs", filename);
5974 /* Concrete subclass of plugin_analyzer_init_iface, allowing plugins
5975 to register new state machines. */
5977 class plugin_analyzer_init_impl : public plugin_analyzer_init_iface
5980 plugin_analyzer_init_impl (auto_delete_vec <state_machine> *checkers,
5981 known_function_manager *known_fn_mgr,
5983 : m_checkers (checkers),
5984 m_known_fn_mgr (known_fn_mgr),
5988 void register_state_machine (std::unique_ptr<state_machine> sm) final override
5990 LOG_SCOPE (m_logger);
5991 m_checkers->safe_push (sm.release ());
5994 void register_known_function (const char *name,
5995 std::unique_ptr<known_function> kf) final override
5997 LOG_SCOPE (m_logger);
5998 m_known_fn_mgr->add (name, std::move (kf));
6001 logger *get_logger () const final override
6007 auto_delete_vec <state_machine> *m_checkers;
6008 known_function_manager *m_known_fn_mgr;
6012 /* Run the analysis "engine". */
6015 impl_run_checkers (logger *logger)
6021 logger->log ("BITS_BIG_ENDIAN: %i", BITS_BIG_ENDIAN ? 1 : 0);
6022 logger->log ("BYTES_BIG_ENDIAN: %i", BYTES_BIG_ENDIAN ? 1 : 0);
6023 logger->log ("WORDS_BIG_ENDIAN: %i", WORDS_BIG_ENDIAN ? 1 : 0);
6024 log_stashed_constants (logger);
6027 /* If using LTO, ensure that the cgraph nodes have function bodies. */
6029 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
6030 node->get_untransformed_body ();
6032 /* Create the supergraph. */
6033 supergraph sg (logger);
6035 engine eng (&sg, logger);
6037 state_purge_map *purge_map = NULL;
6039 if (flag_analyzer_state_purge)
6040 purge_map = new state_purge_map (sg, eng.get_model_manager (), logger);
6042 if (flag_dump_analyzer_supergraph)
6044 /* Dump supergraph pre-analysis. */
6045 auto_timevar tv (TV_ANALYZER_DUMP);
6046 char *filename = concat (dump_base_name, ".supergraph.dot", NULL);
6047 supergraph::dump_args_t args ((enum supergraph_dot_flags)0, NULL);
6048 sg.dump_dot (filename, args);
6052 if (flag_dump_analyzer_state_purge)
6054 auto_timevar tv (TV_ANALYZER_DUMP);
6055 state_purge_annotator a (purge_map);
6056 char *filename = concat (dump_base_name, ".state-purge.dot", NULL);
6057 supergraph::dump_args_t args ((enum supergraph_dot_flags)0, &a);
6058 sg.dump_dot (filename, args);
6062 auto_delete_vec <state_machine> checkers;
6063 make_checkers (checkers, logger);
6065 register_known_functions (*eng.get_known_function_manager ());
6067 plugin_analyzer_init_impl data (&checkers,
6068 eng.get_known_function_manager (),
6070 invoke_plugin_callbacks (PLUGIN_ANALYZER_INIT, &data);
6076 FOR_EACH_VEC_ELT (checkers, i, sm)
6077 logger->log ("checkers[%i]: %s", i, sm->get_name ());
6080 /* Extrinsic state shared by nodes in the graph. */
6081 const extrinsic_state ext_state (checkers, &eng, logger);
6083 const analysis_plan plan (sg, logger);
6085 /* The exploded graph. */
6086 exploded_graph eg (sg, logger, ext_state, purge_map, plan,
6087 analyzer_verbosity);
6089 /* Add entrypoints to the graph for externally-callable functions. */
6090 eg.build_initial_worklist ();
6092 /* Now process the worklist, exploring the <point, state> graph. */
6093 eg.process_worklist ();
6095 if (flag_dump_analyzer_exploded_graph)
6097 auto_timevar tv (TV_ANALYZER_DUMP);
6099 = concat (dump_base_name, ".eg.dot", NULL);
6100 exploded_graph::dump_args_t args (eg);
6102 eg.dump_dot (filename, &c, args);
6106 /* Now emit any saved diagnostics. */
6107 eg.get_diagnostic_manager ().emit_saved_diagnostics (eg);
6109 eg.dump_exploded_nodes ();
6113 if (flag_dump_analyzer_callgraph)
6114 dump_callgraph (sg, &eg);
6116 if (flag_dump_analyzer_supergraph)
6118 /* Dump post-analysis form of supergraph. */
6119 auto_timevar tv (TV_ANALYZER_DUMP);
6120 char *filename = concat (dump_base_name, ".supergraph-eg.dot", NULL);
6121 exploded_graph_annotator a (eg);
6122 supergraph::dump_args_t args ((enum supergraph_dot_flags)0, &a);
6123 sg.dump_dot (filename, args);
6127 if (flag_dump_analyzer_json)
6128 dump_analyzer_json (sg, eg);
6130 if (flag_dump_analyzer_untracked)
6131 eng.get_model_manager ()->dump_untracked_regions ();
6136 /* Handle -fdump-analyzer and -fdump-analyzer-stderr. */
6137 static FILE *dump_fout = NULL;
6139 /* Track if we're responsible for closing dump_fout. */
6140 static bool owns_dump_fout = false;
6142 /* If dumping is enabled, attempt to create dump_fout if it hasn't already
6143 been opened. Return it. */
6146 get_or_create_any_logfile ()
6150 if (flag_dump_analyzer_stderr)
6152 else if (flag_dump_analyzer)
6154 char *dump_filename = concat (dump_base_name, ".analyzer.txt", NULL);
6155 dump_fout = fopen (dump_filename, "w");
6156 free (dump_filename);
6158 owns_dump_fout = true;
6164 /* External entrypoint to the analysis "engine".
6165 Set up any dumps, then call impl_run_checkers. */
6170 /* Save input_location. */
6171 location_t saved_input_location = input_location;
6174 log_user the_logger (NULL);
6175 get_or_create_any_logfile ();
6177 the_logger.set_logger (new logger (dump_fout, 0, 0,
6178 *global_dc->printer));
6179 LOG_SCOPE (the_logger.get_logger ());
6181 impl_run_checkers (the_logger.get_logger ());
6183 /* end of lifetime of the_logger (so that dump file is closed after the
6184 various dtors run). */
6190 owns_dump_fout = false;
6194 /* Restore input_location. Subsequent passes may assume that input_location
6195 is some arbitrary value *not* in the block tree, which might be violated
6196 if we didn't restore it. */
6197 input_location = saved_input_location;
6202 #endif /* #if ENABLE_ANALYZER */