1 /* The analysis "engine".
2 Copyright (C) 2019-2023 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");
129 bool terminate_path
= d
->terminate_path_p ();
130 if (m_eg
->get_diagnostic_manager ().add_diagnostic
131 (m_enode_for_diag
, m_enode_for_diag
->get_supernode (),
132 m_stmt
, m_stmt_finder
, std::move (d
)))
136 && flag_analyzer_suppress_followups
)
137 m_path_ctxt
->terminate_path ();
145 impl_region_model_context::add_note (std::unique_ptr
<pending_note
> pn
)
147 LOG_FUNC (get_logger ());
149 m_eg
->get_diagnostic_manager ().add_note (std::move (pn
));
153 impl_region_model_context::on_svalue_leak (const svalue
*sval
)
156 for (sm_state_map
*smap
: m_new_state
->m_checker_states
)
157 smap
->on_svalue_leak (sval
, this);
161 impl_region_model_context::
162 on_liveness_change (const svalue_set
&live_svalues
,
163 const region_model
*model
)
165 for (sm_state_map
*smap
: m_new_state
->m_checker_states
)
166 smap
->on_liveness_change (live_svalues
, model
, this);
170 impl_region_model_context::on_unknown_change (const svalue
*sval
,
173 if (!sval
->can_have_associated_state_p ())
175 for (sm_state_map
*smap
: m_new_state
->m_checker_states
)
176 smap
->on_unknown_change (sval
, is_mutable
, m_ext_state
);
180 impl_region_model_context::on_escaped_function (tree fndecl
)
182 m_eg
->on_escaped_function (fndecl
);
186 impl_region_model_context::get_uncertainty ()
188 return m_uncertainty
;
191 /* Purge state involving SVAL. The region_model has already been purged,
192 so we only need to purge other state in the program_state:
196 impl_region_model_context::purge_state_involving (const svalue
*sval
)
200 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, i
, smap
)
201 smap
->purge_state_involving (sval
, m_ext_state
);
205 impl_region_model_context::bifurcate (std::unique_ptr
<custom_edge_info
> info
)
208 m_path_ctxt
->bifurcate (std::move (info
));
212 impl_region_model_context::terminate_path ()
215 return m_path_ctxt
->terminate_path ();
218 /* struct setjmp_record. */
221 setjmp_record::cmp (const setjmp_record
&rec1
, const setjmp_record
&rec2
)
223 if (int cmp_enode
= rec1
.m_enode
->m_index
- rec2
.m_enode
->m_index
)
225 gcc_assert (&rec1
== &rec2
);
229 /* class setjmp_svalue : public svalue. */
231 /* Implementation of svalue::accept vfunc for setjmp_svalue. */
234 setjmp_svalue::accept (visitor
*v
) const
236 v
->visit_setjmp_svalue (this);
239 /* Implementation of svalue::dump_to_pp vfunc for setjmp_svalue. */
242 setjmp_svalue::dump_to_pp (pretty_printer
*pp
, bool simple
) const
245 pp_printf (pp
, "SETJMP(EN: %i)", get_enode_index ());
247 pp_printf (pp
, "setjmp_svalue(EN%i)", get_enode_index ());
250 /* Get the index of the stored exploded_node. */
253 setjmp_svalue::get_enode_index () const
255 return m_setjmp_record
.m_enode
->m_index
;
258 /* Concrete implementation of sm_context, wiring it up to the rest of this
261 class impl_sm_context
: public sm_context
264 impl_sm_context (exploded_graph
&eg
,
266 const state_machine
&sm
,
267 exploded_node
*enode_for_diag
,
268 const program_state
*old_state
,
269 program_state
*new_state
,
270 const sm_state_map
*old_smap
,
271 sm_state_map
*new_smap
,
272 path_context
*path_ctxt
,
273 const stmt_finder
*stmt_finder
= NULL
,
274 bool unknown_side_effects
= false)
275 : sm_context (sm_idx
, sm
),
276 m_logger (eg
.get_logger ()),
277 m_eg (eg
), m_enode_for_diag (enode_for_diag
),
278 m_old_state (old_state
), m_new_state (new_state
),
279 m_old_smap (old_smap
), m_new_smap (new_smap
),
280 m_path_ctxt (path_ctxt
),
281 m_stmt_finder (stmt_finder
),
282 m_unknown_side_effects (unknown_side_effects
)
286 logger
*get_logger () const { return m_logger
.get_logger (); }
288 tree
get_fndecl_for_call (const gcall
*call
) final override
290 impl_region_model_context old_ctxt
291 (m_eg
, m_enode_for_diag
, NULL
, NULL
, NULL
/*m_enode->get_state ()*/,
293 region_model
*model
= m_new_state
->m_region_model
;
294 return model
->get_fndecl_for_call (call
, &old_ctxt
);
297 state_machine::state_t
get_state (const gimple
*stmt ATTRIBUTE_UNUSED
,
298 tree var
) final override
300 logger
* const logger
= get_logger ();
302 /* Use NULL ctxt on this get_rvalue call to avoid triggering
303 uninitialized value warnings. */
304 const svalue
*var_old_sval
305 = m_old_state
->m_region_model
->get_rvalue (var
, NULL
);
307 state_machine::state_t current
308 = m_old_smap
->get_state (var_old_sval
, m_eg
.get_ext_state ());
311 state_machine::state_t
get_state (const gimple
*stmt ATTRIBUTE_UNUSED
,
312 const svalue
*sval
) final override
314 logger
* const logger
= get_logger ();
316 state_machine::state_t current
317 = m_old_smap
->get_state (sval
, m_eg
.get_ext_state ());
322 void set_next_state (const gimple
*,
324 state_machine::state_t to
,
325 tree origin
) final override
327 logger
* const logger
= get_logger ();
329 const svalue
*var_new_sval
330 = m_new_state
->m_region_model
->get_rvalue (var
, NULL
);
331 const svalue
*origin_new_sval
332 = m_new_state
->m_region_model
->get_rvalue (origin
, NULL
);
334 /* We use the new sval here to avoid issues with uninitialized values. */
335 state_machine::state_t current
336 = m_old_smap
->get_state (var_new_sval
, m_eg
.get_ext_state ());
338 logger
->log ("%s: state transition of %qE: %s -> %s",
341 current
->get_name (),
343 m_new_smap
->set_state (m_new_state
->m_region_model
, var_new_sval
,
344 to
, origin_new_sval
, m_eg
.get_ext_state ());
347 void set_next_state (const gimple
*stmt
,
349 state_machine::state_t to
,
350 tree origin
) final override
352 logger
* const logger
= get_logger ();
354 impl_region_model_context old_ctxt
355 (m_eg
, m_enode_for_diag
, NULL
, NULL
, NULL
/*m_enode->get_state ()*/,
358 const svalue
*origin_new_sval
359 = m_new_state
->m_region_model
->get_rvalue (origin
, NULL
);
361 state_machine::state_t current
362 = m_old_smap
->get_state (sval
, m_eg
.get_ext_state ());
365 logger
->start_log_line ();
366 logger
->log_partial ("%s: state transition of ",
368 sval
->dump_to_pp (logger
->get_printer (), true);
369 logger
->log_partial (": %s -> %s",
370 current
->get_name (),
372 logger
->end_log_line ();
374 m_new_smap
->set_state (m_new_state
->m_region_model
, sval
,
375 to
, origin_new_sval
, m_eg
.get_ext_state ());
378 void warn (const supernode
*snode
, const gimple
*stmt
,
380 std::unique_ptr
<pending_diagnostic
> d
) final override
382 LOG_FUNC (get_logger ());
384 const svalue
*var_old_sval
385 = m_old_state
->m_region_model
->get_rvalue (var
, NULL
);
386 state_machine::state_t current
388 ? m_old_smap
->get_state (var_old_sval
, m_eg
.get_ext_state ())
389 : m_old_smap
->get_global_state ());
390 bool terminate_path
= d
->terminate_path_p ();
391 m_eg
.get_diagnostic_manager ().add_diagnostic
392 (&m_sm
, m_enode_for_diag
, snode
, stmt
, m_stmt_finder
,
393 var
, var_old_sval
, current
, std::move (d
));
396 && flag_analyzer_suppress_followups
)
397 m_path_ctxt
->terminate_path ();
400 void warn (const supernode
*snode
, const gimple
*stmt
,
402 std::unique_ptr
<pending_diagnostic
> d
) final override
404 LOG_FUNC (get_logger ());
406 state_machine::state_t current
408 ? m_old_smap
->get_state (sval
, m_eg
.get_ext_state ())
409 : m_old_smap
->get_global_state ());
410 bool terminate_path
= d
->terminate_path_p ();
411 m_eg
.get_diagnostic_manager ().add_diagnostic
412 (&m_sm
, m_enode_for_diag
, snode
, stmt
, m_stmt_finder
,
413 NULL_TREE
, sval
, current
, std::move (d
));
416 && flag_analyzer_suppress_followups
)
417 m_path_ctxt
->terminate_path ();
420 /* Hook for picking more readable trees for SSA names of temporaries,
421 so that rather than e.g.
422 "double-free of '<unknown>'"
424 "double-free of 'inbuf.data'". */
426 tree
get_diagnostic_tree (tree expr
) final override
428 /* Only for SSA_NAMEs of temporaries; otherwise, return EXPR, as it's
429 likely to be the least surprising tree to report. */
430 if (TREE_CODE (expr
) != SSA_NAME
)
432 if (SSA_NAME_VAR (expr
) != NULL
)
435 gcc_assert (m_new_state
);
436 const svalue
*sval
= m_new_state
->m_region_model
->get_rvalue (expr
, NULL
);
437 /* Find trees for all regions storing the value. */
438 if (tree t
= m_new_state
->m_region_model
->get_representative_tree (sval
))
444 tree
get_diagnostic_tree (const svalue
*sval
) final override
446 return m_new_state
->m_region_model
->get_representative_tree (sval
);
449 state_machine::state_t
get_global_state () const final override
451 return m_old_state
->m_checker_states
[m_sm_idx
]->get_global_state ();
454 void set_global_state (state_machine::state_t state
) final override
456 m_new_state
->m_checker_states
[m_sm_idx
]->set_global_state (state
);
459 void on_custom_transition (custom_transition
*transition
) final override
461 transition
->impl_transition (&m_eg
,
462 const_cast<exploded_node
*> (m_enode_for_diag
),
466 tree
is_zero_assignment (const gimple
*stmt
) final override
468 const gassign
*assign_stmt
= dyn_cast
<const gassign
*> (stmt
);
471 impl_region_model_context old_ctxt
472 (m_eg
, m_enode_for_diag
, m_old_state
, m_new_state
, NULL
, NULL
, stmt
);
473 if (const svalue
*sval
474 = m_new_state
->m_region_model
->get_gassign_result (assign_stmt
,
476 if (tree cst
= sval
->maybe_get_constant ())
478 return gimple_assign_lhs (assign_stmt
);
482 path_context
*get_path_context () const final override
487 bool unknown_side_effects_p () const final override
489 return m_unknown_side_effects
;
492 const program_state
*get_old_program_state () const final override
497 const program_state
*get_new_program_state () const final override
503 exploded_graph
&m_eg
;
504 exploded_node
*m_enode_for_diag
;
505 const program_state
*m_old_state
;
506 program_state
*m_new_state
;
507 const sm_state_map
*m_old_smap
;
508 sm_state_map
*m_new_smap
;
509 path_context
*m_path_ctxt
;
510 const stmt_finder
*m_stmt_finder
;
512 /* Are we handling an external function with unknown side effects? */
513 bool m_unknown_side_effects
;
517 impl_region_model_context::
518 get_state_map_by_name (const char *name
,
519 sm_state_map
**out_smap
,
520 const state_machine
**out_sm
,
521 unsigned *out_sm_idx
,
522 std::unique_ptr
<sm_context
> *out_sm_context
)
528 if (!m_ext_state
.get_sm_idx_by_name (name
, &sm_idx
))
531 const state_machine
*sm
= &m_ext_state
.get_sm (sm_idx
);
532 sm_state_map
*new_smap
= m_new_state
->m_checker_states
[sm_idx
];
534 *out_smap
= new_smap
;
537 *out_sm_idx
= sm_idx
;
540 const sm_state_map
*old_smap
= m_old_state
->m_checker_states
[sm_idx
];
542 = make_unique
<impl_sm_context
> (*m_eg
,
557 /* Subclass of stmt_finder for finding the best stmt to report the leak at,
558 given the emission path. */
560 class leak_stmt_finder
: public stmt_finder
563 leak_stmt_finder (const exploded_graph
&eg
, tree var
)
564 : m_eg (eg
), m_var (var
) {}
566 std::unique_ptr
<stmt_finder
> clone () const final override
568 return make_unique
<leak_stmt_finder
> (m_eg
, m_var
);
571 const gimple
*find_stmt (const exploded_path
&epath
)
574 logger
* const logger
= m_eg
.get_logger ();
577 if (m_var
&& TREE_CODE (m_var
) == SSA_NAME
)
579 /* Locate the final write to this SSA name in the path. */
580 const gimple
*def_stmt
= SSA_NAME_DEF_STMT (m_var
);
583 bool found
= epath
.find_stmt_backwards (def_stmt
, &idx_of_def_stmt
);
587 /* What was the next write to the underlying var
588 after the SSA name was set? (if any). */
590 for (unsigned idx
= idx_of_def_stmt
+ 1;
591 idx
< epath
.m_edges
.length ();
594 const exploded_edge
*eedge
= epath
.m_edges
[idx
];
596 logger
->log ("eedge[%i]: EN %i -> EN %i",
598 eedge
->m_src
->m_index
,
599 eedge
->m_dest
->m_index
);
600 const exploded_node
*dst_node
= eedge
->m_dest
;
601 const program_point
&dst_point
= dst_node
->get_point ();
602 const gimple
*stmt
= dst_point
.get_stmt ();
605 if (const gassign
*assign
= dyn_cast
<const gassign
*> (stmt
))
607 tree lhs
= gimple_assign_lhs (assign
);
608 if (TREE_CODE (lhs
) == SSA_NAME
609 && SSA_NAME_VAR (lhs
) == SSA_NAME_VAR (m_var
))
617 /* Look backwards for the first statement with a location. */
619 const exploded_edge
*eedge
;
620 FOR_EACH_VEC_ELT_REVERSE (epath
.m_edges
, i
, eedge
)
623 logger
->log ("eedge[%i]: EN %i -> EN %i",
625 eedge
->m_src
->m_index
,
626 eedge
->m_dest
->m_index
);
627 const exploded_node
*dst_node
= eedge
->m_dest
;
628 const program_point
&dst_point
= dst_node
->get_point ();
629 const gimple
*stmt
= dst_point
.get_stmt ();
631 if (get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
640 const exploded_graph
&m_eg
;
644 /* A measurement of how good EXPR is for presenting to the user, so
645 that e.g. we can say prefer printing
646 "leak of 'tmp.m_ptr'"
648 "leak of '<unknown>'". */
651 readability (const_tree expr
)
653 /* Arbitrarily-chosen "high readability" value. */
654 const int HIGH_READABILITY
= 65536;
657 switch (TREE_CODE (expr
))
661 /* Impose a slight readability penalty relative to that of
663 return readability (TREE_OPERAND (expr
, 0)) - 16;
667 if (tree var
= SSA_NAME_VAR (expr
))
669 if (DECL_ARTIFICIAL (var
))
671 /* If we have an SSA name for an artificial var,
672 only use it if it has a debug expr associated with
673 it that fixup_tree_for_diagnostic can use. */
674 if (VAR_P (var
) && DECL_HAS_DEBUG_EXPR_P (var
))
675 return readability (DECL_DEBUG_EXPR (var
)) - 1;
679 /* Slightly favor the underlying var over the SSA name to
680 avoid having them compare equal. */
681 return readability (var
) - 1;
684 /* Avoid printing '<unknown>' for SSA names for temporaries. */
691 if (DECL_NAME (expr
))
692 return HIGH_READABILITY
;
694 /* We don't want to print temporaries. For example, the C FE
695 prints them as e.g. "<Uxxxx>" where "xxxx" is the low 16 bits
696 of the tree pointer (see pp_c_tree_decl_identifier). */
700 /* Printing "<return-value>" isn't ideal, but is less awful than
701 trying to print a temporary. */
702 return HIGH_READABILITY
/ 2;
706 /* Impose a moderate readability penalty for casts. */
707 const int CAST_PENALTY
= 32;
708 return readability (TREE_OPERAND (expr
, 0)) - CAST_PENALTY
;
712 return HIGH_READABILITY
;
721 /* A qsort comparator for trees to sort them into most user-readable to
722 least user-readable. */
725 readability_comparator (const void *p1
, const void *p2
)
727 path_var pv1
= *(path_var
const *)p1
;
728 path_var pv2
= *(path_var
const *)p2
;
730 const int tree_r1
= readability (pv1
.m_tree
);
731 const int tree_r2
= readability (pv2
.m_tree
);
733 /* Favor items that are deeper on the stack and hence more recent;
734 this also favors locals over globals. */
735 const int COST_PER_FRAME
= 64;
736 const int depth_r1
= pv1
.m_stack_depth
* COST_PER_FRAME
;
737 const int depth_r2
= pv2
.m_stack_depth
* COST_PER_FRAME
;
739 /* Combine the scores from the tree and from the stack depth.
740 This e.g. lets us have a slightly penalized cast in the most
741 recent stack frame "beat" an uncast value in an older stack frame. */
742 const int sum_r1
= tree_r1
+ depth_r1
;
743 const int sum_r2
= tree_r2
+ depth_r2
;
744 if (int cmp
= sum_r2
- sum_r1
)
747 /* Otherwise, more readable trees win. */
748 if (int cmp
= tree_r2
- tree_r1
)
751 /* Otherwise, if they have the same readability, then impose an
752 arbitrary deterministic ordering on them. */
754 if (int cmp
= TREE_CODE (pv1
.m_tree
) - TREE_CODE (pv2
.m_tree
))
757 switch (TREE_CODE (pv1
.m_tree
))
762 if (int cmp
= (SSA_NAME_VERSION (pv1
.m_tree
)
763 - SSA_NAME_VERSION (pv2
.m_tree
)))
769 if (int cmp
= DECL_UID (pv1
.m_tree
) - DECL_UID (pv2
.m_tree
))
774 /* TODO: We ought to find ways of sorting such cases. */
778 /* Return true is SNODE is the EXIT node of a function, or is one
779 of the final snodes within its function.
781 Specifically, handle the final supernodes before the EXIT node,
782 for the case of clobbers that happen immediately before exiting.
783 We need a run of snodes leading to the return_p snode, where all edges are
784 intraprocedural, and every snode has just one successor.
786 We use this when suppressing leak reports at the end of "main". */
789 returning_from_function_p (const supernode
*snode
)
795 const supernode
*iter
= snode
;
798 if (iter
->return_p ())
800 if (iter
->m_succs
.length () != 1)
802 const superedge
*sedge
= iter
->m_succs
[0];
803 if (sedge
->get_kind () != SUPEREDGE_CFG_EDGE
)
805 iter
= sedge
->m_dest
;
807 /* Impose a limit to ensure we terminate for pathological cases.
809 We only care about the final 3 nodes, due to cases like:
811 (clobber causing leak)
823 /* Find the best tree for SVAL and call SM's on_leak vfunc with it.
824 If on_leak returns a pending_diagnostic, queue it up to be reported,
825 so that we potentially complain about a leak of SVAL in the given STATE. */
828 impl_region_model_context::on_state_leak (const state_machine
&sm
,
830 state_machine::state_t state
)
832 logger
* const logger
= get_logger ();
836 logger
->start_log_line ();
837 logger
->log_partial ("considering leak of ");
838 sval
->dump_to_pp (logger
->get_printer (), true);
839 logger
->end_log_line ();
845 /* m_old_state also needs to be non-NULL so that the sm_ctxt can look
846 up the old state of SVAL. */
847 gcc_assert (m_old_state
);
849 /* SVAL has leaked within the new state: it is not used by any reachable
851 We need to convert it back to a tree, but since it's likely no regions
852 use it, we have to find the "best" tree for it in the old_state. */
855 = m_old_state
->m_region_model
->get_representative_path_var (sval
,
858 /* Strip off top-level casts */
859 if (leaked_pv
.m_tree
&& TREE_CODE (leaked_pv
.m_tree
) == NOP_EXPR
)
860 leaked_pv
.m_tree
= TREE_OPERAND (leaked_pv
.m_tree
, 0);
862 /* This might be NULL; the pending_diagnostic subclasses need to cope
864 tree leaked_tree
= leaked_pv
.m_tree
;
868 logger
->log ("best leaked_tree: %qE", leaked_tree
);
870 logger
->log ("best leaked_tree: NULL");
873 leak_stmt_finder
stmt_finder (*m_eg
, leaked_tree
);
874 gcc_assert (m_enode_for_diag
);
876 /* Don't complain about leaks when returning from "main". */
877 if (returning_from_function_p (m_enode_for_diag
->get_supernode ()))
879 tree fndecl
= m_enode_for_diag
->get_function ()->decl
;
880 if (id_equal (DECL_NAME (fndecl
), "main"))
883 logger
->log ("not reporting leak from main");
888 tree leaked_tree_for_diag
= fixup_tree_for_diagnostic (leaked_tree
);
889 std::unique_ptr
<pending_diagnostic
> pd
= sm
.on_leak (leaked_tree_for_diag
);
891 m_eg
->get_diagnostic_manager ().add_diagnostic
892 (&sm
, m_enode_for_diag
, m_enode_for_diag
->get_supernode (),
893 m_stmt
, &stmt_finder
,
894 leaked_tree_for_diag
, sval
, state
, std::move (pd
));
897 /* Implementation of region_model_context::on_condition vfunc.
898 Notify all state machines about the condition, which could lead to
899 state transitions. */
902 impl_region_model_context::on_condition (const svalue
*lhs
,
908 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
910 const state_machine
&sm
= m_ext_state
.get_sm (sm_idx
);
911 impl_sm_context
sm_ctxt (*m_eg
, sm_idx
, sm
, m_enode_for_diag
,
912 m_old_state
, m_new_state
,
913 m_old_state
->m_checker_states
[sm_idx
],
914 m_new_state
->m_checker_states
[sm_idx
],
916 sm
.on_condition (&sm_ctxt
,
918 ? m_enode_for_diag
->get_supernode ()
925 /* Implementation of region_model_context::on_bounded_ranges vfunc.
926 Notify all state machines about the ranges, which could lead to
927 state transitions. */
930 impl_region_model_context::on_bounded_ranges (const svalue
&sval
,
931 const bounded_ranges
&ranges
)
935 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
937 const state_machine
&sm
= m_ext_state
.get_sm (sm_idx
);
938 impl_sm_context
sm_ctxt (*m_eg
, sm_idx
, sm
, m_enode_for_diag
,
939 m_old_state
, m_new_state
,
940 m_old_state
->m_checker_states
[sm_idx
],
941 m_new_state
->m_checker_states
[sm_idx
],
943 sm
.on_bounded_ranges (&sm_ctxt
,
945 ? m_enode_for_diag
->get_supernode ()
947 m_stmt
, sval
, ranges
);
951 /* Implementation of region_model_context::on_pop_frame vfunc.
952 Notify all state machines about the frame being popped, which
953 could lead to states being discarded. */
956 impl_region_model_context::on_pop_frame (const frame_region
*frame_reg
)
960 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
962 const state_machine
&sm
= m_ext_state
.get_sm (sm_idx
);
963 sm
.on_pop_frame (smap
, frame_reg
);
967 /* Implementation of region_model_context::on_phi vfunc.
968 Notify all state machines about the phi, which could lead to
969 state transitions. */
972 impl_region_model_context::on_phi (const gphi
*phi
, tree rhs
)
976 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
978 const state_machine
&sm
= m_ext_state
.get_sm (sm_idx
);
979 impl_sm_context
sm_ctxt (*m_eg
, sm_idx
, sm
, m_enode_for_diag
,
980 m_old_state
, m_new_state
,
981 m_old_state
->m_checker_states
[sm_idx
],
982 m_new_state
->m_checker_states
[sm_idx
],
984 sm
.on_phi (&sm_ctxt
, m_enode_for_diag
->get_supernode (), phi
, rhs
);
988 /* Implementation of region_model_context::on_unexpected_tree_code vfunc.
989 Mark the new state as being invalid for further exploration.
990 TODO(stage1): introduce a warning for when this occurs. */
993 impl_region_model_context::on_unexpected_tree_code (tree t
,
994 const dump_location_t
&loc
)
996 logger
* const logger
= get_logger ();
998 logger
->log ("unhandled tree code: %qs in %qs at %s:%i",
999 get_tree_code_name (TREE_CODE (t
)),
1000 loc
.get_impl_location ().m_function
,
1001 loc
.get_impl_location ().m_file
,
1002 loc
.get_impl_location ().m_line
);
1004 m_new_state
->m_valid
= false;
1007 /* struct point_and_state. */
1009 /* Assert that this object is sane. */
1012 point_and_state::validate (const extrinsic_state
&ext_state
) const
1014 /* Skip this in a release build. */
1019 m_point
.validate ();
1021 m_state
.validate (ext_state
);
1023 /* Verify that the callstring's model of the stack corresponds to that
1024 of the region_model. */
1025 /* They should have the same depth. */
1026 gcc_assert (m_point
.get_stack_depth ()
1027 == m_state
.m_region_model
->get_stack_depth ());
1028 /* Check the functions in the callstring vs those in the frames
1030 for (const frame_region
*iter_frame
1031 = m_state
.m_region_model
->get_current_frame ();
1032 iter_frame
; iter_frame
= iter_frame
->get_calling_frame ())
1034 int index
= iter_frame
->get_index ();
1035 gcc_assert (m_point
.get_function_at_depth (index
)
1036 == iter_frame
->get_function ());
1040 /* Subroutine of print_enode_indices: print a run of indices from START_IDX
1041 to END_IDX to PP, using and updating *FIRST_RUN. */
1044 print_run (pretty_printer
*pp
, int start_idx
, int end_idx
,
1048 pp_string (pp
, ", ");
1050 if (start_idx
== end_idx
)
1051 pp_printf (pp
, "EN: %i", start_idx
);
1053 pp_printf (pp
, "EN: %i-%i", start_idx
, end_idx
);
1056 /* Print the indices within ENODES to PP, collecting them as
1057 runs/singletons e.g. "EN: 4-7, EN: 20-23, EN: 42". */
1060 print_enode_indices (pretty_printer
*pp
,
1061 const auto_vec
<exploded_node
*> &enodes
)
1063 int cur_start_idx
= -1;
1064 int cur_finish_idx
= -1;
1065 bool first_run
= true;
1067 exploded_node
*enode
;
1068 FOR_EACH_VEC_ELT (enodes
, i
, enode
)
1070 if (cur_start_idx
== -1)
1072 gcc_assert (cur_finish_idx
== -1);
1073 cur_start_idx
= cur_finish_idx
= enode
->m_index
;
1077 if (enode
->m_index
== cur_finish_idx
+ 1)
1078 /* Continuation of a run. */
1079 cur_finish_idx
= enode
->m_index
;
1082 /* Finish existing run, start a new one. */
1083 gcc_assert (cur_start_idx
>= 0);
1084 gcc_assert (cur_finish_idx
>= 0);
1085 print_run (pp
, cur_start_idx
, cur_finish_idx
,
1087 cur_start_idx
= cur_finish_idx
= enode
->m_index
;
1091 /* Finish any existing run. */
1092 if (cur_start_idx
>= 0)
1094 gcc_assert (cur_finish_idx
>= 0);
1095 print_run (pp
, cur_start_idx
, cur_finish_idx
,
1100 /* struct eg_traits::dump_args_t. */
1102 /* The <FILENAME>.eg.dot output can quickly become unwieldy if we show
1103 full details for all enodes (both in terms of CPU time to render it,
1104 and in terms of being meaningful to a human viewing it).
1106 If we show just the IDs then the resulting graph is usually viewable,
1107 but then we have to keep switching back and forth between the .dot
1108 view and other dumps.
1110 This function implements a heuristic for showing detail at the enodes
1111 that (we hope) matter, and just the ID at other enodes, fixing the CPU
1112 usage of the .dot viewer, and drawing the attention of the viewer
1115 Return true if ENODE should be shown in detail in .dot output.
1116 Return false if no detail should be shown for ENODE. */
1119 eg_traits::dump_args_t::show_enode_details_p (const exploded_node
&enode
) const
1121 /* If the number of exploded nodes isn't too large, we may as well show
1122 all enodes in full detail in the .dot output. */
1123 if (m_eg
.m_nodes
.length ()
1124 <= (unsigned) param_analyzer_max_enodes_for_full_dump
)
1127 /* Otherwise, assume that what's most interesting are state explosions,
1128 and thus the places where this happened.
1129 Expand enodes at program points where we hit the per-enode limit, so we
1130 can investigate what exploded. */
1131 const per_program_point_data
*per_point_data
1132 = m_eg
.get_per_program_point_data (enode
.get_point ());
1133 return per_point_data
->m_excess_enodes
> 0;
1136 /* class exploded_node : public dnode<eg_traits>. */
1139 exploded_node::status_to_str (enum status s
)
1143 default: gcc_unreachable ();
1144 case STATUS_WORKLIST
: return "WORKLIST";
1145 case STATUS_PROCESSED
: return "PROCESSED";
1146 case STATUS_MERGER
: return "MERGER";
1147 case STATUS_BULK_MERGED
: return "BULK_MERGED";
1151 /* exploded_node's ctor. */
1153 exploded_node::exploded_node (const point_and_state
&ps
,
1155 : m_ps (ps
), m_status (STATUS_WORKLIST
), m_index (index
),
1156 m_num_processed_stmts (0)
1158 gcc_checking_assert (ps
.get_state ().m_region_model
->canonicalized_p ());
1161 /* Get the stmt that was processed in this enode at index IDX.
1162 IDX is an index within the stmts processed at this enode, rather
1163 than within those of the supernode. */
1166 exploded_node::get_processed_stmt (unsigned idx
) const
1168 gcc_assert (idx
< m_num_processed_stmts
);
1169 const program_point
&point
= get_point ();
1170 gcc_assert (point
.get_kind () == PK_BEFORE_STMT
);
1171 const supernode
*snode
= get_supernode ();
1172 const unsigned int point_stmt_idx
= point
.get_stmt_idx ();
1173 const unsigned int idx_within_snode
= point_stmt_idx
+ idx
;
1174 const gimple
*stmt
= snode
->m_stmts
[idx_within_snode
];
1178 /* For use by dump_dot, get a value for the .dot "fillcolor" attribute.
1179 Colorize by sm-state, to make it easier to see how sm-state propagates
1180 through the exploded_graph. */
1183 exploded_node::get_dot_fillcolor () const
1185 const program_state
&state
= get_state ();
1187 /* We want to be able to easily distinguish the no-sm-state case,
1188 and to be able to distinguish cases where there's a single state
1191 Sum the sm_states, and use the result to choose from a table,
1192 modulo table-size, special-casing the "no sm-state" case. */
1193 int total_sm_state
= 0;
1196 FOR_EACH_VEC_ELT (state
.m_checker_states
, i
, smap
)
1198 for (sm_state_map::iterator_t iter
= smap
->begin ();
1199 iter
!= smap
->end ();
1201 total_sm_state
+= (*iter
).second
.m_state
->get_id ();
1202 total_sm_state
+= smap
->get_global_state ()->get_id ();
1205 if (total_sm_state
> 0)
1207 /* An arbitrarily-picked collection of light colors. */
1208 const char * const colors
[]
1209 = {"azure", "coral", "cornsilk", "lightblue", "yellow",
1210 "honeydew", "lightpink", "lightsalmon", "palegreen1",
1211 "wheat", "seashell"};
1212 const int num_colors
= ARRAY_SIZE (colors
);
1213 return colors
[total_sm_state
% num_colors
];
1220 /* Implementation of dnode::dump_dot vfunc for exploded_node. */
1223 exploded_node::dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const
1225 pretty_printer
*pp
= gv
->get_pp ();
1228 pp_printf (pp
, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
1229 get_dot_fillcolor ());
1230 pp_write_text_to_stream (pp
);
1232 pp_printf (pp
, "EN: %i", m_index
);
1233 if (m_status
== STATUS_MERGER
)
1234 pp_string (pp
, " (merger)");
1235 else if (m_status
== STATUS_BULK_MERGED
)
1236 pp_string (pp
, " (bulk merged)");
1239 if (args
.show_enode_details_p (*this))
1242 m_ps
.get_point ().print (pp
, f
);
1245 const extrinsic_state
&ext_state
= args
.m_eg
.get_ext_state ();
1246 const program_state
&state
= m_ps
.get_state ();
1247 state
.dump_to_pp (ext_state
, false, true, pp
);
1250 dump_processed_stmts (pp
);
1253 dump_saved_diagnostics (pp
);
1255 args
.dump_extra_info (this, pp
);
1257 pp_write_text_as_dot_label_to_stream (pp
, /*for_record=*/true);
1259 pp_string (pp
, "\"];\n\n");
1261 /* It can be hard to locate the saved diagnostics as text within the
1262 enode nodes, so add extra nodes to the graph for each saved_diagnostic,
1264 Compare with dump_saved_diagnostics. */
1267 const saved_diagnostic
*sd
;
1268 FOR_EACH_VEC_ELT (m_saved_diagnostics
, i
, sd
)
1270 sd
->dump_as_dot_node (pp
);
1272 /* Add edge connecting this enode to the saved_diagnostic. */
1274 pp_string (pp
, " -> ");
1275 sd
->dump_dot_id (pp
);
1276 pp_string (pp
, " [style=\"dotted\" arrowhead=\"none\"];");
1284 /* Show any stmts that were processed within this enode,
1285 and their index within the supernode. */
1287 exploded_node::dump_processed_stmts (pretty_printer
*pp
) const
1289 if (m_num_processed_stmts
> 0)
1291 const program_point
&point
= get_point ();
1292 gcc_assert (point
.get_kind () == PK_BEFORE_STMT
);
1293 const supernode
*snode
= get_supernode ();
1294 const unsigned int point_stmt_idx
= point
.get_stmt_idx ();
1296 pp_printf (pp
, "stmts: %i", m_num_processed_stmts
);
1298 for (unsigned i
= 0; i
< m_num_processed_stmts
; i
++)
1300 const unsigned int idx_within_snode
= point_stmt_idx
+ i
;
1301 const gimple
*stmt
= snode
->m_stmts
[idx_within_snode
];
1302 pp_printf (pp
, " %i: ", idx_within_snode
);
1303 pp_gimple_stmt_1 (pp
, stmt
, 0, (dump_flags_t
)0);
1309 /* Dump any saved_diagnostics at this enode to PP. */
1312 exploded_node::dump_saved_diagnostics (pretty_printer
*pp
) const
1315 const saved_diagnostic
*sd
;
1316 FOR_EACH_VEC_ELT (m_saved_diagnostics
, i
, sd
)
1318 pp_printf (pp
, "DIAGNOSTIC: %s (sd: %i)",
1319 sd
->m_d
->get_kind (), sd
->get_index ());
1324 /* Dump this to PP in a form suitable for use as an id in .dot output. */
1327 exploded_node::dump_dot_id (pretty_printer
*pp
) const
1329 pp_printf (pp
, "exploded_node_%i", m_index
);
1332 /* Dump a multiline representation of this node to PP. */
1335 exploded_node::dump_to_pp (pretty_printer
*pp
,
1336 const extrinsic_state
&ext_state
) const
1338 pp_printf (pp
, "EN: %i", m_index
);
1342 m_ps
.get_point ().print (pp
, f
);
1345 m_ps
.get_state ().dump_to_pp (ext_state
, false, true, pp
);
1349 /* Dump a multiline representation of this node to FILE. */
1352 exploded_node::dump (FILE *fp
,
1353 const extrinsic_state
&ext_state
) const
1356 pp_format_decoder (&pp
) = default_tree_printer
;
1357 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
1358 pp
.buffer
->stream
= fp
;
1359 dump_to_pp (&pp
, ext_state
);
1363 /* Dump a multiline representation of this node to stderr. */
1366 exploded_node::dump (const extrinsic_state
&ext_state
) const
1368 dump (stderr
, ext_state
);
1371 /* Return a new json::object of the form
1372 {"point" : object for program_point,
1373 "state" : object for program_state,
1376 "processed_stmts" : int}. */
1379 exploded_node::to_json (const extrinsic_state
&ext_state
) const
1381 json::object
*enode_obj
= new json::object ();
1383 enode_obj
->set ("point", get_point ().to_json ());
1384 enode_obj
->set ("state", get_state ().to_json (ext_state
));
1385 enode_obj
->set ("status", new json::string (status_to_str (m_status
)));
1386 enode_obj
->set ("idx", new json::integer_number (m_index
));
1387 enode_obj
->set ("processed_stmts",
1388 new json::integer_number (m_num_processed_stmts
));
1395 /* Return true if FNDECL has a gimple body. */
1396 // TODO: is there a pre-canned way to do this?
1399 fndecl_has_gimple_body_p (tree fndecl
)
1401 if (fndecl
== NULL_TREE
)
1404 cgraph_node
*n
= cgraph_node::get (fndecl
);
1408 return n
->has_gimple_body_p ();
1413 /* Modify STATE in place, applying the effects of the stmt at this node's
1416 exploded_node::on_stmt_flags
1417 exploded_node::on_stmt (exploded_graph
&eg
,
1418 const supernode
*snode
,
1420 program_state
*state
,
1421 uncertainty_t
*uncertainty
,
1422 path_context
*path_ctxt
)
1424 logger
*logger
= eg
.get_logger ();
1428 logger
->start_log_line ();
1429 pp_gimple_stmt_1 (logger
->get_printer (), stmt
, 0, (dump_flags_t
)0);
1430 logger
->end_log_line ();
1433 /* Update input_location in case of ICE: make it easier to track down which
1434 source construct we're failing to handle. */
1435 input_location
= stmt
->location
;
1437 gcc_assert (state
->m_region_model
);
1439 /* Preserve the old state. It is used here for looking
1440 up old checker states, for determining state transitions, and
1441 also within impl_region_model_context and impl_sm_context for
1442 going from tree to svalue_id. */
1443 const program_state
old_state (*state
);
1445 impl_region_model_context
ctxt (eg
, this,
1446 &old_state
, state
, uncertainty
,
1449 /* Handle call summaries here. */
1450 if (cgraph_edge
*cgedge
1451 = supergraph_call_edge (snode
->get_function (), stmt
))
1452 if (eg
.get_analysis_plan ().use_summary_p (cgedge
))
1454 function
*called_fn
= get_ultimate_function_for_cgraph_edge (cgedge
);
1455 per_function_data
*called_fn_data
1456 = eg
.get_per_function_data (called_fn
);
1458 return replay_call_summaries (eg
,
1460 as_a
<const gcall
*> (stmt
),
1468 bool unknown_side_effects
= false;
1469 bool terminate_path
= false;
1471 on_stmt_pre (eg
, stmt
, state
, &terminate_path
,
1472 &unknown_side_effects
, &ctxt
);
1475 return on_stmt_flags::terminate_path ();
1479 FOR_EACH_VEC_ELT (old_state
.m_checker_states
, sm_idx
, smap
)
1481 const state_machine
&sm
= eg
.get_ext_state ().get_sm (sm_idx
);
1482 const sm_state_map
*old_smap
1483 = old_state
.m_checker_states
[sm_idx
];
1484 sm_state_map
*new_smap
= state
->m_checker_states
[sm_idx
];
1485 impl_sm_context
sm_ctxt (eg
, sm_idx
, sm
, this, &old_state
, state
,
1486 old_smap
, new_smap
, path_ctxt
, NULL
,
1487 unknown_side_effects
);
1489 /* Allow the state_machine to handle the stmt. */
1490 if (sm
.on_stmt (&sm_ctxt
, snode
, stmt
))
1491 unknown_side_effects
= false;
1494 if (path_ctxt
->terminate_path_p ())
1495 return on_stmt_flags::terminate_path ();
1497 on_stmt_post (stmt
, state
, unknown_side_effects
, &ctxt
);
1499 return on_stmt_flags ();
1502 /* Handle the pre-sm-state part of STMT, modifying STATE in-place.
1503 Write true to *OUT_TERMINATE_PATH if the path should be terminated.
1504 Write true to *OUT_UNKNOWN_SIDE_EFFECTS if the stmt has unknown
1508 exploded_node::on_stmt_pre (exploded_graph
&eg
,
1510 program_state
*state
,
1511 bool *out_terminate_path
,
1512 bool *out_unknown_side_effects
,
1513 region_model_context
*ctxt
)
1515 /* Handle special-case calls that require the full program_state. */
1516 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
1518 if (is_special_named_call_p (call
, "__analyzer_dump", 0))
1520 /* Handle the builtin "__analyzer_dump" by dumping state
1522 state
->dump (eg
.get_ext_state (), true);
1525 else if (is_special_named_call_p (call
, "__analyzer_dump_state", 2))
1527 state
->impl_call_analyzer_dump_state (call
, eg
.get_ext_state (),
1531 else if (is_setjmp_call_p (call
))
1533 state
->m_region_model
->on_setjmp (call
, this, ctxt
);
1536 else if (is_longjmp_call_p (call
))
1538 on_longjmp (eg
, call
, state
, ctxt
);
1539 *out_terminate_path
= true;
1544 /* Otherwise, defer to m_region_model. */
1545 state
->m_region_model
->on_stmt_pre (stmt
,
1546 out_unknown_side_effects
,
1550 /* Handle the post-sm-state part of STMT, modifying STATE in-place. */
1553 exploded_node::on_stmt_post (const gimple
*stmt
,
1554 program_state
*state
,
1555 bool unknown_side_effects
,
1556 region_model_context
*ctxt
)
1558 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
1559 state
->m_region_model
->on_call_post (call
, unknown_side_effects
, ctxt
);
1562 /* A concrete call_info subclass representing a replay of a call summary. */
1564 class call_summary_edge_info
: public call_info
1567 call_summary_edge_info (const call_details
&cd
,
1568 function
*called_fn
,
1569 call_summary
*summary
,
1570 const extrinsic_state
&ext_state
)
1572 m_called_fn (called_fn
),
1573 m_summary (summary
),
1574 m_ext_state (ext_state
)
1577 bool update_state (program_state
*state
,
1578 const exploded_edge
*,
1579 region_model_context
*ctxt
) const final override
1581 /* Update STATE based on summary_end_state. */
1582 call_details
cd (get_call_details (state
->m_region_model
, ctxt
));
1583 call_summary_replay
r (cd
, m_called_fn
, m_summary
, m_ext_state
);
1584 const program_state
&summary_end_state
= m_summary
->get_state ();
1585 return state
->replay_call_summary (r
, summary_end_state
);
1588 bool update_model (region_model
*model
,
1589 const exploded_edge
*,
1590 region_model_context
*ctxt
) const final override
1592 /* Update STATE based on summary_end_state. */
1593 call_details
cd (get_call_details (model
, ctxt
));
1594 call_summary_replay
r (cd
, m_called_fn
, m_summary
, m_ext_state
);
1595 const program_state
&summary_end_state
= m_summary
->get_state ();
1596 model
->replay_call_summary (r
, *summary_end_state
.m_region_model
);
1600 label_text
get_desc (bool /*can_colorize*/) const final override
1602 return m_summary
->get_desc ();
1606 function
*m_called_fn
;
1607 call_summary
*m_summary
;
1608 const extrinsic_state
&m_ext_state
;
1611 /* Use PATH_CTXT to bifurcate, which when handled will add custom edges
1612 for a replay of the various feasible summaries in CALLED_FN_DATA. */
1614 exploded_node::on_stmt_flags
1615 exploded_node::replay_call_summaries (exploded_graph
&eg
,
1616 const supernode
*snode
,
1617 const gcall
*call_stmt
,
1618 program_state
*state
,
1619 path_context
*path_ctxt
,
1620 function
*called_fn
,
1621 per_function_data
*called_fn_data
,
1622 region_model_context
*ctxt
)
1624 logger
*logger
= eg
.get_logger ();
1627 gcc_assert (called_fn
);
1628 gcc_assert (called_fn_data
);
1630 /* Each summary will call bifurcate on the PATH_CTXT. */
1631 for (auto summary
: called_fn_data
->m_summaries
)
1632 replay_call_summary (eg
, snode
, call_stmt
, state
,
1633 path_ctxt
, called_fn
, summary
, ctxt
);
1634 path_ctxt
->terminate_path ();
1636 return on_stmt_flags ();
1639 /* Use PATH_CTXT to bifurcate, which when handled will add a
1640 custom edge for a replay of SUMMARY, if the summary's
1641 conditions are feasible based on the current state. */
1644 exploded_node::replay_call_summary (exploded_graph
&eg
,
1645 const supernode
*snode
,
1646 const gcall
*call_stmt
,
1647 program_state
*old_state
,
1648 path_context
*path_ctxt
,
1649 function
*called_fn
,
1650 call_summary
*summary
,
1651 region_model_context
*ctxt
)
1653 logger
*logger
= eg
.get_logger ();
1656 gcc_assert (call_stmt
);
1657 gcc_assert (old_state
);
1658 gcc_assert (called_fn
);
1659 gcc_assert (summary
);
1662 logger
->log ("using %s as summary for call to %qE from %qE",
1663 summary
->get_desc ().get (),
1665 snode
->get_function ()->decl
);
1666 const extrinsic_state
&ext_state
= eg
.get_ext_state ();
1667 const program_state
&summary_end_state
= summary
->get_state ();
1670 pretty_printer
*pp
= logger
->get_printer ();
1672 logger
->start_log_line ();
1673 pp_string (pp
, "callsite state: ");
1674 old_state
->dump_to_pp (ext_state
, true, false, pp
);
1675 logger
->end_log_line ();
1677 logger
->start_log_line ();
1678 pp_string (pp
, "summary end state: ");
1679 summary_end_state
.dump_to_pp (ext_state
, true, false, pp
);
1680 logger
->end_log_line ();
1683 program_state
new_state (*old_state
);
1685 call_details
cd (call_stmt
, new_state
.m_region_model
, ctxt
);
1686 call_summary_replay
r (cd
, called_fn
, summary
, ext_state
);
1689 path_ctxt
->bifurcate (make_unique
<call_summary_edge_info
> (cd
,
1696 /* Consider the effect of following superedge SUCC from this node.
1698 Return true if it's feasible to follow the edge, or false
1701 Examples: if it's the "true" branch within
1702 a CFG and we know the conditional is false, we know it's infeasible.
1703 If it's one of multiple interprocedual "return" edges, then only
1704 the edge back to the most recent callsite is feasible.
1706 Update NEXT_STATE accordingly (e.g. to record that a condition was
1707 true or false, or that the NULL-ness of a pointer has been checked,
1708 pushing/popping stack frames, etc).
1710 Update NEXT_POINT accordingly (updating the call string). */
1713 exploded_node::on_edge (exploded_graph
&eg
,
1714 const superedge
*succ
,
1715 program_point
*next_point
,
1716 program_state
*next_state
,
1717 uncertainty_t
*uncertainty
)
1719 LOG_FUNC (eg
.get_logger ());
1721 if (!next_point
->on_edge (eg
, succ
))
1724 if (!next_state
->on_edge (eg
, this, succ
, uncertainty
))
1730 /* Verify that the stack at LONGJMP_POINT is still valid, given a call
1731 to "setjmp" at SETJMP_POINT - the stack frame that "setjmp" was
1732 called in must still be valid.
1734 Caveat: this merely checks the call_strings in the points; it doesn't
1735 detect the case where a frame returns and is then called again. */
1738 valid_longjmp_stack_p (const program_point
&longjmp_point
,
1739 const program_point
&setjmp_point
)
1741 const call_string
&cs_at_longjmp
= longjmp_point
.get_call_string ();
1742 const call_string
&cs_at_setjmp
= setjmp_point
.get_call_string ();
1744 if (cs_at_longjmp
.length () < cs_at_setjmp
.length ())
1747 /* Check that the call strings match, up to the depth of the
1749 for (unsigned depth
= 0; depth
< cs_at_setjmp
.length (); depth
++)
1750 if (cs_at_longjmp
[depth
] != cs_at_setjmp
[depth
])
1756 /* A pending_diagnostic subclass for complaining about bad longjmps,
1757 where the enclosing function of the "setjmp" has returned (and thus
1758 the stack frame no longer exists). */
1760 class stale_jmp_buf
: public pending_diagnostic_subclass
<stale_jmp_buf
>
1763 stale_jmp_buf (const gcall
*setjmp_call
, const gcall
*longjmp_call
,
1764 const program_point
&setjmp_point
)
1765 : m_setjmp_call (setjmp_call
), m_longjmp_call (longjmp_call
),
1766 m_setjmp_point (setjmp_point
), m_stack_pop_event (NULL
)
1769 int get_controlling_option () const final override
1771 return OPT_Wanalyzer_stale_setjmp_buffer
;
1774 bool emit (rich_location
*richloc
, logger
*) final override
1777 (richloc
, get_controlling_option (),
1778 "%qs called after enclosing function of %qs has returned",
1779 get_user_facing_name (m_longjmp_call
),
1780 get_user_facing_name (m_setjmp_call
));
1783 const char *get_kind () const final override
1784 { return "stale_jmp_buf"; }
1786 bool operator== (const stale_jmp_buf
&other
) const
1788 return (m_setjmp_call
== other
.m_setjmp_call
1789 && m_longjmp_call
== other
.m_longjmp_call
);
1793 maybe_add_custom_events_for_superedge (const exploded_edge
&eedge
,
1794 checker_path
*emission_path
)
1797 /* Detect exactly when the stack first becomes invalid,
1798 and issue an event then. */
1799 if (m_stack_pop_event
)
1801 const exploded_node
*src_node
= eedge
.m_src
;
1802 const program_point
&src_point
= src_node
->get_point ();
1803 const exploded_node
*dst_node
= eedge
.m_dest
;
1804 const program_point
&dst_point
= dst_node
->get_point ();
1805 if (valid_longjmp_stack_p (src_point
, m_setjmp_point
)
1806 && !valid_longjmp_stack_p (dst_point
, m_setjmp_point
))
1808 /* Compare with diagnostic_manager::add_events_for_superedge. */
1809 const int src_stack_depth
= src_point
.get_stack_depth ();
1810 m_stack_pop_event
= new precanned_custom_event
1811 (event_loc_info (src_point
.get_location (),
1812 src_point
.get_fndecl (),
1814 "stack frame is popped here, invalidating saved environment");
1815 emission_path
->add_event
1816 (std::unique_ptr
<custom_event
> (m_stack_pop_event
));
1822 label_text
describe_final_event (const evdesc::final_event
&ev
) final override
1824 if (m_stack_pop_event
)
1825 return ev
.formatted_print
1826 ("%qs called after enclosing function of %qs returned at %@",
1827 get_user_facing_name (m_longjmp_call
),
1828 get_user_facing_name (m_setjmp_call
),
1829 m_stack_pop_event
->get_id_ptr ());
1831 return ev
.formatted_print
1832 ("%qs called after enclosing function of %qs has returned",
1833 get_user_facing_name (m_longjmp_call
),
1834 get_user_facing_name (m_setjmp_call
));;
1839 const gcall
*m_setjmp_call
;
1840 const gcall
*m_longjmp_call
;
1841 program_point m_setjmp_point
;
1842 custom_event
*m_stack_pop_event
;
1845 /* Handle LONGJMP_CALL, a call to longjmp or siglongjmp.
1847 Attempt to locate where setjmp/sigsetjmp was called on the jmp_buf and build
1848 an exploded_node and exploded_edge to it representing a rewind to that frame,
1849 handling the various kinds of failure that can occur. */
1852 exploded_node::on_longjmp (exploded_graph
&eg
,
1853 const gcall
*longjmp_call
,
1854 program_state
*new_state
,
1855 region_model_context
*ctxt
)
1857 tree buf_ptr
= gimple_call_arg (longjmp_call
, 0);
1858 gcc_assert (POINTER_TYPE_P (TREE_TYPE (buf_ptr
)));
1860 region_model
*new_region_model
= new_state
->m_region_model
;
1861 const svalue
*buf_ptr_sval
= new_region_model
->get_rvalue (buf_ptr
, ctxt
);
1862 const region
*buf
= new_region_model
->deref_rvalue (buf_ptr_sval
, buf_ptr
,
1865 const svalue
*buf_content_sval
1866 = new_region_model
->get_store_value (buf
, ctxt
);
1867 const setjmp_svalue
*setjmp_sval
1868 = buf_content_sval
->dyn_cast_setjmp_svalue ();
1872 const setjmp_record tmp_setjmp_record
= setjmp_sval
->get_setjmp_record ();
1874 /* Build a custom enode and eedge for rewinding from the longjmp/siglongjmp
1875 call back to the setjmp/sigsetjmp. */
1876 rewind_info_t
rewind_info (tmp_setjmp_record
, longjmp_call
);
1878 const gcall
*setjmp_call
= rewind_info
.get_setjmp_call ();
1879 const program_point
&setjmp_point
= rewind_info
.get_setjmp_point ();
1881 const program_point
&longjmp_point
= get_point ();
1883 /* Verify that the setjmp's call_stack hasn't been popped. */
1884 if (!valid_longjmp_stack_p (longjmp_point
, setjmp_point
))
1886 ctxt
->warn (make_unique
<stale_jmp_buf
> (setjmp_call
,
1892 gcc_assert (longjmp_point
.get_stack_depth ()
1893 >= setjmp_point
.get_stack_depth ());
1895 /* Update the state for use by the destination node. */
1897 /* Stash the current number of diagnostics so that we can update
1898 any that this adds to show where the longjmp is rewinding to. */
1900 diagnostic_manager
*dm
= &eg
.get_diagnostic_manager ();
1901 unsigned prev_num_diagnostics
= dm
->get_num_diagnostics ();
1903 new_region_model
->on_longjmp (longjmp_call
, setjmp_call
,
1904 setjmp_point
.get_stack_depth (), ctxt
);
1906 /* Detect leaks in the new state relative to the old state. */
1907 program_state::detect_leaks (get_state (), *new_state
, NULL
,
1908 eg
.get_ext_state (), ctxt
);
1910 program_point next_point
1911 = program_point::after_supernode (setjmp_point
.get_supernode (),
1912 setjmp_point
.get_call_string ());
1915 = eg
.get_or_create_node (next_point
, *new_state
, this);
1917 /* Create custom exploded_edge for a longjmp. */
1920 exploded_edge
*eedge
1921 = eg
.add_edge (const_cast<exploded_node
*> (this), next
, NULL
,
1922 make_unique
<rewind_info_t
> (tmp_setjmp_record
, longjmp_call
));
1924 /* For any diagnostics that were queued here (such as leaks) we want
1925 the checker_path to show the rewinding events after the "final event"
1926 so that the user sees where the longjmp is rewinding to (otherwise the
1927 path is meaningless).
1929 For example, we want to emit something like:
1931 | NN | longjmp (env, 1);
1932 | | ~~~~~~~~~~~~~~~~
1934 | | (10) 'ptr' leaks here; was allocated at (7)
1935 | | (11) rewinding from 'longjmp' in 'inner'...
1941 | NN | i = setjmp(env);
1944 | | (12) ...to 'setjmp' in 'outer' (saved at (2))
1946 where the "final" event above is event (10), but we want to append
1947 events (11) and (12) afterwards.
1949 Do this by setting m_trailing_eedge on any diagnostics that were
1951 unsigned num_diagnostics
= dm
->get_num_diagnostics ();
1952 for (unsigned i
= prev_num_diagnostics
; i
< num_diagnostics
; i
++)
1954 saved_diagnostic
*sd
= dm
->get_saved_diagnostic (i
);
1955 sd
->m_trailing_eedge
= eedge
;
1960 /* Subroutine of exploded_graph::process_node for finding the successors
1961 of the supernode for a function exit basic block.
1963 Ensure that pop_frame is called, potentially queuing diagnostics about
1967 exploded_node::detect_leaks (exploded_graph
&eg
)
1969 LOG_FUNC_1 (eg
.get_logger (), "EN: %i", m_index
);
1971 gcc_assert (get_point ().get_supernode ()->return_p ());
1973 /* If we're not a "top-level" function, do nothing; pop_frame
1974 will be called when handling the return superedge. */
1975 if (get_point ().get_stack_depth () > 1)
1978 /* We have a "top-level" function. */
1979 gcc_assert (get_point ().get_stack_depth () == 1);
1981 const program_state
&old_state
= get_state ();
1983 /* Work with a temporary copy of the state: pop the frame, and see
1984 what leaks (via purge_unused_svalues). */
1985 program_state
new_state (old_state
);
1987 gcc_assert (new_state
.m_region_model
);
1989 uncertainty_t uncertainty
;
1990 impl_region_model_context
ctxt (eg
, this,
1991 &old_state
, &new_state
, &uncertainty
, NULL
,
1993 const svalue
*result
= NULL
;
1994 new_state
.m_region_model
->pop_frame (NULL
, &result
, &ctxt
);
1995 program_state::detect_leaks (old_state
, new_state
, result
,
1996 eg
.get_ext_state (), &ctxt
);
1999 /* Dump the successors and predecessors of this enode to OUTF. */
2002 exploded_node::dump_succs_and_preds (FILE *outf
) const
2007 auto_vec
<exploded_node
*> preds (m_preds
.length ());
2008 FOR_EACH_VEC_ELT (m_preds
, i
, e
)
2009 preds
.quick_push (e
->m_src
);
2011 print_enode_indices (&pp
, preds
);
2012 fprintf (outf
, "preds: %s\n",
2013 pp_formatted_text (&pp
));
2016 auto_vec
<exploded_node
*> succs (m_succs
.length ());
2017 FOR_EACH_VEC_ELT (m_succs
, i
, e
)
2018 succs
.quick_push (e
->m_dest
);
2020 print_enode_indices (&pp
, succs
);
2021 fprintf (outf
, "succs: %s\n",
2022 pp_formatted_text (&pp
));
2026 /* class dynamic_call_info_t : public custom_edge_info. */
2028 /* Implementation of custom_edge_info::update_model vfunc
2029 for dynamic_call_info_t.
2031 Update state for a dynamically discovered call (or return), by pushing
2032 or popping the a frame for the appropriate function. */
2035 dynamic_call_info_t::update_model (region_model
*model
,
2036 const exploded_edge
*eedge
,
2037 region_model_context
*ctxt
) const
2040 if (m_is_returning_call
)
2041 model
->update_for_return_gcall (m_dynamic_call
, ctxt
);
2044 function
*callee
= eedge
->m_dest
->get_function ();
2045 model
->update_for_gcall (m_dynamic_call
, ctxt
, callee
);
2050 /* Implementation of custom_edge_info::add_events_to_path vfunc
2051 for dynamic_call_info_t. */
2054 dynamic_call_info_t::add_events_to_path (checker_path
*emission_path
,
2055 const exploded_edge
&eedge
) const
2057 const exploded_node
*src_node
= eedge
.m_src
;
2058 const program_point
&src_point
= src_node
->get_point ();
2059 const int src_stack_depth
= src_point
.get_stack_depth ();
2060 const exploded_node
*dest_node
= eedge
.m_dest
;
2061 const program_point
&dest_point
= dest_node
->get_point ();
2062 const int dest_stack_depth
= dest_point
.get_stack_depth ();
2064 if (m_is_returning_call
)
2065 emission_path
->add_event
2066 (make_unique
<return_event
> (eedge
,
2067 event_loc_info (m_dynamic_call
2068 ? m_dynamic_call
->location
2070 dest_point
.get_fndecl (),
2071 dest_stack_depth
)));
2073 emission_path
->add_event
2074 (make_unique
<call_event
> (eedge
,
2075 event_loc_info (m_dynamic_call
2076 ? m_dynamic_call
->location
2078 src_point
.get_fndecl (),
2082 /* class rewind_info_t : public custom_edge_info. */
2084 /* Implementation of custom_edge_info::update_model vfunc
2087 Update state for the special-case of a rewind of a longjmp
2088 to a setjmp (which doesn't have a superedge, but does affect
2092 rewind_info_t::update_model (region_model
*model
,
2093 const exploded_edge
*eedge
,
2094 region_model_context
*) const
2097 const program_point
&longjmp_point
= eedge
->m_src
->get_point ();
2098 const program_point
&setjmp_point
= eedge
->m_dest
->get_point ();
2100 gcc_assert (longjmp_point
.get_stack_depth ()
2101 >= setjmp_point
.get_stack_depth ());
2103 model
->on_longjmp (get_longjmp_call (),
2105 setjmp_point
.get_stack_depth (), NULL
);
2109 /* Implementation of custom_edge_info::add_events_to_path vfunc
2110 for rewind_info_t. */
2113 rewind_info_t::add_events_to_path (checker_path
*emission_path
,
2114 const exploded_edge
&eedge
) const
2116 const exploded_node
*src_node
= eedge
.m_src
;
2117 const program_point
&src_point
= src_node
->get_point ();
2118 const int src_stack_depth
= src_point
.get_stack_depth ();
2119 const exploded_node
*dst_node
= eedge
.m_dest
;
2120 const program_point
&dst_point
= dst_node
->get_point ();
2121 const int dst_stack_depth
= dst_point
.get_stack_depth ();
2123 emission_path
->add_event
2124 (make_unique
<rewind_from_longjmp_event
>
2126 event_loc_info (get_longjmp_call ()->location
,
2127 src_point
.get_fndecl (),
2130 emission_path
->add_event
2131 (make_unique
<rewind_to_setjmp_event
>
2133 event_loc_info (get_setjmp_call ()->location
,
2134 dst_point
.get_fndecl (),
2139 /* class exploded_edge : public dedge<eg_traits>. */
2141 /* exploded_edge's ctor. */
2143 exploded_edge::exploded_edge (exploded_node
*src
, exploded_node
*dest
,
2144 const superedge
*sedge
,
2145 std::unique_ptr
<custom_edge_info
> custom_info
)
2146 : dedge
<eg_traits
> (src
, dest
), m_sedge (sedge
),
2147 m_custom_info (std::move (custom_info
))
2151 /* Implementation of dedge::dump_dot vfunc for exploded_edge.
2152 Use the label of the underlying superedge, if any. */
2155 exploded_edge::dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
2157 pretty_printer
*pp
= gv
->get_pp ();
2159 m_src
->dump_dot_id (pp
);
2160 pp_string (pp
, " -> ");
2161 m_dest
->dump_dot_id (pp
);
2162 dump_dot_label (pp
);
2165 /* Second half of exploded_edge::dump_dot. This is split out
2166 for use by trimmed_graph::dump_dot and base_feasible_edge::dump_dot. */
2169 exploded_edge::dump_dot_label (pretty_printer
*pp
) const
2171 const char *style
= "\"solid,bold\"";
2172 const char *color
= "black";
2174 const char *constraint
= "true";
2177 switch (m_sedge
->m_kind
)
2181 case SUPEREDGE_CFG_EDGE
:
2183 case SUPEREDGE_CALL
:
2185 //constraint = "false";
2187 case SUPEREDGE_RETURN
:
2189 //constraint = "false";
2191 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
2192 style
= "\"dotted\"";
2198 style
= "\"dotted\"";
2202 (" [style=%s, color=%s, weight=%d, constraint=%s,"
2204 style
, color
, weight
, constraint
);
2207 m_sedge
->dump_label_to_pp (pp
, false);
2208 else if (m_custom_info
)
2209 m_custom_info
->print (pp
);
2211 //pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
2213 pp_printf (pp
, "\"];\n");
2216 /* Return a new json::object of the form
2217 {"src_idx": int, the index of the source exploded edge,
2218 "dst_idx": int, the index of the destination exploded edge,
2219 "sedge": (optional) object for the superedge, if any,
2220 "custom": (optional) str, a description, if this is a custom edge}. */
2223 exploded_edge::to_json () const
2225 json::object
*eedge_obj
= new json::object ();
2226 eedge_obj
->set ("src_idx", new json::integer_number (m_src
->m_index
));
2227 eedge_obj
->set ("dst_idx", new json::integer_number (m_dest
->m_index
));
2229 eedge_obj
->set ("sedge", m_sedge
->to_json ());
2233 pp_format_decoder (&pp
) = default_tree_printer
;
2234 m_custom_info
->print (&pp
);
2235 eedge_obj
->set ("custom", new json::string (pp_formatted_text (&pp
)));
2244 stats::stats (int num_supernodes
)
2245 : m_node_reuse_count (0),
2246 m_node_reuse_after_merge_count (0),
2247 m_num_supernodes (num_supernodes
)
2249 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
2253 /* Log these stats in multiline form to LOGGER. */
2256 stats::log (logger
*logger
) const
2258 gcc_assert (logger
);
2259 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
2260 if (m_num_nodes
[i
] > 0)
2261 logger
->log ("m_num_nodes[%s]: %i",
2262 point_kind_to_string (static_cast <enum point_kind
> (i
)),
2264 logger
->log ("m_node_reuse_count: %i", m_node_reuse_count
);
2265 logger
->log ("m_node_reuse_after_merge_count: %i",
2266 m_node_reuse_after_merge_count
);
2269 /* Dump these stats in multiline form to OUT. */
2272 stats::dump (FILE *out
) const
2274 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
2275 if (m_num_nodes
[i
] > 0)
2276 fprintf (out
, "m_num_nodes[%s]: %i\n",
2277 point_kind_to_string (static_cast <enum point_kind
> (i
)),
2279 fprintf (out
, "m_node_reuse_count: %i\n", m_node_reuse_count
);
2280 fprintf (out
, "m_node_reuse_after_merge_count: %i\n",
2281 m_node_reuse_after_merge_count
);
2283 if (m_num_supernodes
> 0)
2284 fprintf (out
, "PK_AFTER_SUPERNODE nodes per supernode: %.2f\n",
2285 (float)m_num_nodes
[PK_AFTER_SUPERNODE
] / (float)m_num_supernodes
);
2288 /* Return the total number of enodes recorded within this object. */
2291 stats::get_total_enodes () const
2294 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
2295 result
+= m_num_nodes
[i
];
2299 /* struct per_function_data. */
2301 per_function_data::~per_function_data ()
2303 for (auto iter
: m_summaries
)
2308 per_function_data::add_call_summary (exploded_node
*node
)
2310 m_summaries
.safe_push (new call_summary (this, node
));
2313 /* strongly_connected_components's ctor. Tarjan's SCC algorithm. */
2315 strongly_connected_components::
2316 strongly_connected_components (const supergraph
&sg
, logger
*logger
)
2317 : m_sg (sg
), m_per_node (m_sg
.num_nodes ())
2320 auto_timevar
tv (TV_ANALYZER_SCC
);
2322 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2323 m_per_node
.quick_push (per_node_data ());
2325 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2326 if (m_per_node
[i
].m_index
== -1)
2333 /* Dump this object to stderr. */
2336 strongly_connected_components::dump () const
2338 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2340 const per_node_data
&v
= m_per_node
[i
];
2341 fprintf (stderr
, "SN %i: index: %i lowlink: %i on_stack: %i\n",
2342 i
, v
.m_index
, v
.m_lowlink
, v
.m_on_stack
);
2346 /* Return a new json::array of per-snode SCC ids. */
2349 strongly_connected_components::to_json () const
2351 json::array
*scc_arr
= new json::array ();
2352 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2353 scc_arr
->append (new json::integer_number (get_scc_id (i
)));
2357 /* Subroutine of strongly_connected_components's ctor, part of Tarjan's
2361 strongly_connected_components::strong_connect (unsigned index
)
2363 supernode
*v_snode
= m_sg
.get_node_by_index (index
);
2365 /* Set the depth index for v to the smallest unused index. */
2366 per_node_data
*v
= &m_per_node
[index
];
2368 v
->m_lowlink
= index
;
2369 m_stack
.safe_push (index
);
2370 v
->m_on_stack
= true;
2373 /* Consider successors of v. */
2376 FOR_EACH_VEC_ELT (v_snode
->m_succs
, i
, sedge
)
2378 if (sedge
->get_kind () != SUPEREDGE_CFG_EDGE
2379 && sedge
->get_kind () != SUPEREDGE_INTRAPROCEDURAL_CALL
)
2381 supernode
*w_snode
= sedge
->m_dest
;
2382 per_node_data
*w
= &m_per_node
[w_snode
->m_index
];
2383 if (w
->m_index
== -1)
2385 /* Successor w has not yet been visited; recurse on it. */
2386 strong_connect (w_snode
->m_index
);
2387 v
->m_lowlink
= MIN (v
->m_lowlink
, w
->m_lowlink
);
2389 else if (w
->m_on_stack
)
2391 /* Successor w is in stack S and hence in the current SCC
2392 If w is not on stack, then (v, w) is a cross-edge in the DFS
2393 tree and must be ignored. */
2394 v
->m_lowlink
= MIN (v
->m_lowlink
, w
->m_index
);
2398 /* If v is a root node, pop the stack and generate an SCC. */
2400 if (v
->m_lowlink
== v
->m_index
)
2404 int idx
= m_stack
.pop ();
2405 w
= &m_per_node
[idx
];
2406 w
->m_on_stack
= false;
2411 /* worklist's ctor. */
2413 worklist::worklist (const exploded_graph
&eg
, const analysis_plan
&plan
)
2414 : m_scc (eg
.get_supergraph (), eg
.get_logger ()),
2416 m_queue (key_t (*this, NULL
))
2420 /* Return the number of nodes in the worklist. */
2423 worklist::length () const
2425 return m_queue
.nodes ();
2428 /* Return the next node in the worklist, removing it. */
2431 worklist::take_next ()
2433 return m_queue
.extract_min ();
2436 /* Return the next node in the worklist without removing it. */
2439 worklist::peek_next ()
2441 return m_queue
.min ();
2444 /* Add ENODE to the worklist. */
2447 worklist::add_node (exploded_node
*enode
)
2449 gcc_assert (enode
->get_status () == exploded_node::STATUS_WORKLIST
);
2450 m_queue
.insert (key_t (*this, enode
), enode
);
2453 /* Comparator for implementing worklist::key_t comparison operators.
2454 Return negative if KA is before KB
2455 Return positive if KA is after KB
2456 Return 0 if they are equal.
2458 The ordering of the worklist is critical for performance and for
2459 avoiding node explosions. Ideally we want all enodes at a CFG join-point
2460 with the same callstring to be sorted next to each other in the worklist
2461 so that a run of consecutive enodes can be merged and processed "in bulk"
2462 rather than individually or pairwise, minimizing the number of new enodes
2466 worklist::key_t::cmp (const worklist::key_t
&ka
, const worklist::key_t
&kb
)
2468 const program_point
&point_a
= ka
.m_enode
->get_point ();
2469 const program_point
&point_b
= kb
.m_enode
->get_point ();
2470 const call_string
&call_string_a
= point_a
.get_call_string ();
2471 const call_string
&call_string_b
= point_b
.get_call_string ();
2473 /* Order empty-callstring points with different functions based on the
2474 analysis_plan, so that we generate summaries before they are used. */
2475 if (flag_analyzer_call_summaries
2476 && call_string_a
.empty_p ()
2477 && call_string_b
.empty_p ()
2478 && point_a
.get_function () != NULL
2479 && point_b
.get_function () != NULL
2480 && point_a
.get_function () != point_b
.get_function ())
2482 if (int cmp
= ka
.m_worklist
.m_plan
.cmp_function (point_a
.get_function (),
2483 point_b
.get_function ()))
2487 /* Sort by callstring, so that nodes with deeper call strings are processed
2488 before those with shallower call strings.
2497 then we want the path inside the function call to be fully explored up
2498 to the return to the join BB before we explore on the "no fn call" path,
2499 so that both enodes at the join BB reach the front of the worklist at
2500 the same time and thus have a chance of being merged. */
2501 int cs_cmp
= call_string::cmp (call_string_a
, call_string_b
);
2506 int scc_id_a
= ka
.get_scc_id (ka
.m_enode
);
2507 int scc_id_b
= kb
.get_scc_id (kb
.m_enode
);
2508 if (scc_id_a
!= scc_id_b
)
2509 return scc_id_a
- scc_id_b
;
2511 /* If in same SCC, order by supernode index (an arbitrary but stable
2513 const supernode
*snode_a
= ka
.m_enode
->get_supernode ();
2514 const supernode
*snode_b
= kb
.m_enode
->get_supernode ();
2515 if (snode_a
== NULL
)
2517 if (snode_b
!= NULL
)
2521 /* Both are NULL. */
2524 if (snode_b
== NULL
)
2527 /* Neither are NULL. */
2528 gcc_assert (snode_a
&& snode_b
);
2529 if (snode_a
->m_index
!= snode_b
->m_index
)
2530 return snode_a
->m_index
- snode_b
->m_index
;
2532 gcc_assert (snode_a
== snode_b
);
2534 /* Order within supernode via program point. */
2535 int within_snode_cmp
2536 = function_point::cmp_within_supernode (point_a
.get_function_point (),
2537 point_b
.get_function_point ());
2538 if (within_snode_cmp
)
2539 return within_snode_cmp
;
2541 /* Otherwise, we ought to have the same program_point. */
2542 gcc_assert (point_a
== point_b
);
2544 const program_state
&state_a
= ka
.m_enode
->get_state ();
2545 const program_state
&state_b
= kb
.m_enode
->get_state ();
2547 /* Sort by sm-state, so that identical sm-states are grouped
2548 together in the worklist. */
2549 for (unsigned sm_idx
= 0; sm_idx
< state_a
.m_checker_states
.length ();
2552 sm_state_map
*smap_a
= state_a
.m_checker_states
[sm_idx
];
2553 sm_state_map
*smap_b
= state_b
.m_checker_states
[sm_idx
];
2555 if (int smap_cmp
= sm_state_map::cmp (*smap_a
, *smap_b
))
2559 /* Otherwise, we have two enodes at the same program point but with
2560 different states. We don't have a good total ordering on states,
2561 so order them by enode index, so that we have at least have a
2563 return ka
.m_enode
->m_index
- kb
.m_enode
->m_index
;
2566 /* Return a new json::object of the form
2567 {"scc" : [per-snode-IDs]}, */
2570 worklist::to_json () const
2572 json::object
*worklist_obj
= new json::object ();
2574 worklist_obj
->set ("scc", m_scc
.to_json ());
2576 /* The following field isn't yet being JSONified:
2579 return worklist_obj
;
2582 /* exploded_graph's ctor. */
2584 exploded_graph::exploded_graph (const supergraph
&sg
, logger
*logger
,
2585 const extrinsic_state
&ext_state
,
2586 const state_purge_map
*purge_map
,
2587 const analysis_plan
&plan
,
2589 : m_sg (sg
), m_logger (logger
),
2590 m_worklist (*this, plan
),
2591 m_ext_state (ext_state
),
2592 m_purge_map (purge_map
),
2594 m_diagnostic_manager (logger
, ext_state
.get_engine (), verbosity
),
2595 m_global_stats (m_sg
.num_nodes ()),
2596 m_functionless_stats (m_sg
.num_nodes ()),
2597 m_PK_AFTER_SUPERNODE_per_snode (m_sg
.num_nodes ())
2599 m_origin
= get_or_create_node
2600 (program_point::origin (*ext_state
.get_model_manager ()),
2601 program_state (ext_state
), NULL
);
2602 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2603 m_PK_AFTER_SUPERNODE_per_snode
.quick_push (i
);
2606 /* exploded_graph's dtor. */
2608 exploded_graph::~exploded_graph ()
2610 for (auto iter
: m_per_point_data
)
2612 for (auto iter
: m_per_function_data
)
2614 for (auto iter
: m_per_function_stats
)
2616 for (auto iter
: m_per_call_string_data
)
2620 /* Subroutine for use when implementing __attribute__((tainted_args))
2621 on functions and on function pointer fields in structs.
2623 Called on STATE representing a call to FNDECL.
2624 Mark all params of FNDECL in STATE as "tainted". Mark the value of all
2625 regions pointed to by params of FNDECL as "tainted".
2627 Return true if successful; return false if the "taint" state machine
2631 mark_params_as_tainted (program_state
*state
, tree fndecl
,
2632 const extrinsic_state
&ext_state
)
2634 unsigned taint_sm_idx
;
2635 if (!ext_state
.get_sm_idx_by_name ("taint", &taint_sm_idx
))
2637 sm_state_map
*smap
= state
->m_checker_states
[taint_sm_idx
];
2639 const state_machine
&sm
= ext_state
.get_sm (taint_sm_idx
);
2640 state_machine::state_t tainted
= sm
.get_state_by_name ("tainted");
2642 region_model_manager
*mgr
= ext_state
.get_model_manager ();
2644 function
*fun
= DECL_STRUCT_FUNCTION (fndecl
);
2647 for (tree iter_parm
= DECL_ARGUMENTS (fndecl
); iter_parm
;
2648 iter_parm
= DECL_CHAIN (iter_parm
))
2650 tree param
= iter_parm
;
2651 if (tree parm_default_ssa
= ssa_default_def (fun
, iter_parm
))
2652 param
= parm_default_ssa
;
2653 const region
*param_reg
= state
->m_region_model
->get_lvalue (param
, NULL
);
2654 const svalue
*init_sval
= mgr
->get_or_create_initial_value (param_reg
);
2655 smap
->set_state (state
->m_region_model
, init_sval
,
2656 tainted
, NULL
/*origin_new_sval*/, ext_state
);
2657 if (POINTER_TYPE_P (TREE_TYPE (param
)))
2659 const region
*pointee_reg
= mgr
->get_symbolic_region (init_sval
);
2660 /* Mark "*param" as tainted. */
2661 const svalue
*init_pointee_sval
2662 = mgr
->get_or_create_initial_value (pointee_reg
);
2663 smap
->set_state (state
->m_region_model
, init_pointee_sval
,
2664 tainted
, NULL
/*origin_new_sval*/, ext_state
);
2671 /* Custom event for use by tainted_args_function_info when a function
2672 has been marked with __attribute__((tainted_args)). */
2674 class tainted_args_function_custom_event
: public custom_event
2677 tainted_args_function_custom_event (const event_loc_info
&loc_info
)
2678 : custom_event (loc_info
),
2679 m_fndecl (loc_info
.m_fndecl
)
2683 label_text
get_desc (bool can_colorize
) const final override
2685 return make_label_text
2687 "function %qE marked with %<__attribute__((tainted_args))%>",
2695 /* Custom exploded_edge info for top-level calls to a function
2696 marked with __attribute__((tainted_args)). */
2698 class tainted_args_function_info
: public custom_edge_info
2701 tainted_args_function_info (tree fndecl
)
2705 void print (pretty_printer
*pp
) const final override
2707 pp_string (pp
, "call to tainted_args function");
2710 bool update_model (region_model
*,
2711 const exploded_edge
*,
2712 region_model_context
*) const final override
2718 void add_events_to_path (checker_path
*emission_path
,
2719 const exploded_edge
&) const final override
2721 emission_path
->add_event
2722 (make_unique
<tainted_args_function_custom_event
>
2723 (event_loc_info (DECL_SOURCE_LOCATION (m_fndecl
), m_fndecl
, 0)));
2730 /* Ensure that there is an exploded_node representing an external call to
2731 FUN, adding it to the worklist if creating it.
2733 Add an edge from the origin exploded_node to the function entrypoint
2736 Return the exploded_node for the entrypoint to the function. */
2739 exploded_graph::add_function_entry (function
*fun
)
2741 gcc_assert (gimple_has_body_p (fun
->decl
));
2743 /* Be idempotent. */
2744 if (m_functions_with_enodes
.contains (fun
))
2746 logger
* const logger
= get_logger ();
2748 logger
->log ("entrypoint for %qE already exists", fun
->decl
);
2753 = program_point::from_function_entry (*m_ext_state
.get_model_manager (),
2755 program_state
state (m_ext_state
);
2756 state
.push_frame (m_ext_state
, fun
);
2758 std::unique_ptr
<custom_edge_info
> edge_info
= NULL
;
2760 if (lookup_attribute ("tainted_args", DECL_ATTRIBUTES (fun
->decl
)))
2762 if (mark_params_as_tainted (&state
, fun
->decl
, m_ext_state
))
2763 edge_info
= make_unique
<tainted_args_function_info
> (fun
->decl
);
2769 exploded_node
*enode
= get_or_create_node (point
, state
, NULL
);
2773 add_edge (m_origin
, enode
, NULL
, std::move (edge_info
));
2775 m_functions_with_enodes
.add (fun
);
2780 /* Get or create an exploded_node for (POINT, STATE).
2781 If a new node is created, it is added to the worklist.
2783 Use ENODE_FOR_DIAG, a pre-existing enode, for any diagnostics
2784 that need to be emitted (e.g. when purging state *before* we have
2788 exploded_graph::get_or_create_node (const program_point
&point
,
2789 const program_state
&state
,
2790 exploded_node
*enode_for_diag
)
2792 logger
* const logger
= get_logger ();
2797 pretty_printer
*pp
= logger
->get_printer ();
2798 logger
->start_log_line ();
2799 pp_string (pp
, "point: ");
2800 point
.print (pp
, f
);
2801 logger
->end_log_line ();
2802 logger
->start_log_line ();
2803 pp_string (pp
, "state: ");
2804 state
.dump_to_pp (m_ext_state
, true, false, pp
);
2805 logger
->end_log_line ();
2808 /* Stop exploring paths for which we don't know how to effectively
2813 logger
->log ("invalid state; not creating node");
2817 auto_cfun
sentinel (point
.get_function ());
2819 state
.validate (get_ext_state ());
2821 //state.dump (get_ext_state ());
2823 /* Prune state to try to improve the chances of a cache hit,
2824 avoiding generating redundant nodes. */
2825 uncertainty_t uncertainty
;
2826 program_state pruned_state
2827 = state
.prune_for_point (*this, point
, enode_for_diag
, &uncertainty
);
2829 pruned_state
.validate (get_ext_state ());
2831 //pruned_state.dump (get_ext_state ());
2835 pretty_printer
*pp
= logger
->get_printer ();
2836 logger
->start_log_line ();
2837 pp_string (pp
, "pruned_state: ");
2838 pruned_state
.dump_to_pp (m_ext_state
, true, false, pp
);
2839 logger
->end_log_line ();
2840 pruned_state
.m_region_model
->dump_to_pp (logger
->get_printer (), true,
2844 stats
*per_fn_stats
= get_or_create_function_stats (point
.get_function ());
2847 = &get_or_create_per_call_string_data (point
.get_call_string ())->m_stats
;
2849 point_and_state
ps (point
, pruned_state
);
2850 ps
.validate (m_ext_state
);
2851 if (exploded_node
**slot
= m_point_and_state_to_node
.get (&ps
))
2853 /* An exploded_node for PS already exists. */
2855 logger
->log ("reused EN: %i", (*slot
)->m_index
);
2856 m_global_stats
.m_node_reuse_count
++;
2857 per_fn_stats
->m_node_reuse_count
++;
2858 per_cs_stats
->m_node_reuse_count
++;
2862 per_program_point_data
*per_point_data
2863 = get_or_create_per_program_point_data (point
);
2865 /* Consider merging state with another enode at this program_point. */
2866 if (flag_analyzer_state_merge
)
2868 exploded_node
*existing_enode
;
2870 FOR_EACH_VEC_ELT (per_point_data
->m_enodes
, i
, existing_enode
)
2873 logger
->log ("considering merging with existing EN: %i for point",
2874 existing_enode
->m_index
);
2875 gcc_assert (existing_enode
->get_point () == point
);
2876 const program_state
&existing_state
= existing_enode
->get_state ();
2878 /* This merges successfully within the loop. */
2880 program_state
merged_state (m_ext_state
);
2881 if (pruned_state
.can_merge_with_p (existing_state
, m_ext_state
, point
,
2884 merged_state
.validate (m_ext_state
);
2886 logger
->log ("merging new state with that of EN: %i",
2887 existing_enode
->m_index
);
2889 /* Try again for a cache hit.
2890 Whether we get one or not, merged_state's value_ids have no
2891 relationship to those of the input state, and thus to those
2892 of CHANGE, so we must purge any svalue_ids from *CHANGE. */
2893 ps
.set_state (merged_state
);
2895 if (exploded_node
**slot
= m_point_and_state_to_node
.get (&ps
))
2897 /* An exploded_node for PS already exists. */
2899 logger
->log ("reused EN: %i", (*slot
)->m_index
);
2900 m_global_stats
.m_node_reuse_after_merge_count
++;
2901 per_fn_stats
->m_node_reuse_after_merge_count
++;
2902 per_cs_stats
->m_node_reuse_after_merge_count
++;
2908 logger
->log ("not merging new state with that of EN: %i",
2909 existing_enode
->m_index
);
2913 /* Impose a limit on the number of enodes per program point, and
2914 simply stop if we exceed it. */
2915 if ((int)per_point_data
->m_enodes
.length ()
2916 >= param_analyzer_max_enodes_per_program_point
)
2919 point
.print (&pp
, format (false));
2920 print_enode_indices (&pp
, per_point_data
->m_enodes
);
2922 logger
->log ("not creating enode; too many at program point: %s",
2923 pp_formatted_text (&pp
));
2924 warning_at (point
.get_location (), OPT_Wanalyzer_too_complex
,
2925 "terminating analysis for this program point: %s",
2926 pp_formatted_text (&pp
));
2927 per_point_data
->m_excess_enodes
++;
2931 ps
.validate (m_ext_state
);
2933 /* An exploded_node for "ps" doesn't already exist; create one. */
2934 exploded_node
*node
= new exploded_node (ps
, m_nodes
.length ());
2936 m_point_and_state_to_node
.put (node
->get_ps_key (), node
);
2938 /* Update per-program_point data. */
2939 per_point_data
->m_enodes
.safe_push (node
);
2941 const enum point_kind node_pk
= node
->get_point ().get_kind ();
2942 m_global_stats
.m_num_nodes
[node_pk
]++;
2943 per_fn_stats
->m_num_nodes
[node_pk
]++;
2944 per_cs_stats
->m_num_nodes
[node_pk
]++;
2946 if (node_pk
== PK_AFTER_SUPERNODE
)
2947 m_PK_AFTER_SUPERNODE_per_snode
[point
.get_supernode ()->m_index
]++;
2952 pretty_printer
*pp
= logger
->get_printer ();
2953 logger
->log ("created EN: %i", node
->m_index
);
2954 logger
->start_log_line ();
2955 pp_string (pp
, "point: ");
2956 point
.print (pp
, f
);
2957 logger
->end_log_line ();
2958 logger
->start_log_line ();
2959 pp_string (pp
, "pruned_state: ");
2960 pruned_state
.dump_to_pp (m_ext_state
, true, false, pp
);
2961 logger
->end_log_line ();
2964 /* Add the new node to the worlist. */
2965 m_worklist
.add_node (node
);
2969 /* Add an exploded_edge from SRC to DEST, recording its association
2970 with SEDGE (which may be NULL), and, if non-NULL, taking ownership
2972 Return the newly-created eedge. */
2975 exploded_graph::add_edge (exploded_node
*src
, exploded_node
*dest
,
2976 const superedge
*sedge
,
2977 std::unique_ptr
<custom_edge_info
> custom_info
)
2980 get_logger ()->log ("creating edge EN: %i -> EN: %i",
2981 src
->m_index
, dest
->m_index
);
2982 exploded_edge
*e
= new exploded_edge (src
, dest
, sedge
,
2983 std::move (custom_info
));
2984 digraph
<eg_traits
>::add_edge (e
);
2988 /* Ensure that this graph has per-program_point-data for POINT;
2989 borrow a pointer to it. */
2991 per_program_point_data
*
2993 get_or_create_per_program_point_data (const program_point
&point
)
2995 if (per_program_point_data
**slot
= m_per_point_data
.get (&point
))
2998 per_program_point_data
*per_point_data
= new per_program_point_data (point
);
2999 m_per_point_data
.put (&per_point_data
->m_key
, per_point_data
);
3000 return per_point_data
;
3003 /* Get this graph's per-program-point-data for POINT if there is any,
3006 per_program_point_data
*
3007 exploded_graph::get_per_program_point_data (const program_point
&point
) const
3009 if (per_program_point_data
**slot
3010 = const_cast <point_map_t
&> (m_per_point_data
).get (&point
))
3016 /* Ensure that this graph has per-call_string-data for CS;
3017 borrow a pointer to it. */
3019 per_call_string_data
*
3020 exploded_graph::get_or_create_per_call_string_data (const call_string
&cs
)
3022 if (per_call_string_data
**slot
= m_per_call_string_data
.get (&cs
))
3025 per_call_string_data
*data
= new per_call_string_data (cs
, m_sg
.num_nodes ());
3026 m_per_call_string_data
.put (&data
->m_key
,
3031 /* Ensure that this graph has per-function-data for FUN;
3032 borrow a pointer to it. */
3035 exploded_graph::get_or_create_per_function_data (function
*fun
)
3037 if (per_function_data
**slot
= m_per_function_data
.get (fun
))
3040 per_function_data
*data
= new per_function_data ();
3041 m_per_function_data
.put (fun
, data
);
3045 /* Get this graph's per-function-data for FUN if there is any,
3049 exploded_graph::get_per_function_data (function
*fun
) const
3051 if (per_function_data
**slot
3052 = const_cast <per_function_data_t
&> (m_per_function_data
).get (fun
))
3058 /* Return true if FUN should be traversed directly, rather than only as
3059 called via other functions. */
3062 toplevel_function_p (function
*fun
, logger
*logger
)
3064 /* Don't directly traverse into functions that have an "__analyzer_"
3065 prefix. Doing so is useful for the analyzer test suite, allowing
3066 us to have functions that are called in traversals, but not directly
3067 explored, thus testing how the analyzer handles calls and returns.
3068 With this, we can have DejaGnu directives that cover just the case
3069 of where a function is called by another function, without generating
3070 excess messages from the case of the first function being traversed
3072 #define ANALYZER_PREFIX "__analyzer_"
3073 if (!strncmp (IDENTIFIER_POINTER (DECL_NAME (fun
->decl
)), ANALYZER_PREFIX
,
3074 strlen (ANALYZER_PREFIX
)))
3077 logger
->log ("not traversing %qE (starts with %qs)",
3078 fun
->decl
, ANALYZER_PREFIX
);
3083 logger
->log ("traversing %qE (all checks passed)", fun
->decl
);
3088 /* Custom event for use by tainted_call_info when a callback field has been
3089 marked with __attribute__((tainted_args)), for labelling the field. */
3091 class tainted_args_field_custom_event
: public custom_event
3094 tainted_args_field_custom_event (tree field
)
3095 : custom_event (event_loc_info (DECL_SOURCE_LOCATION (field
), NULL_TREE
, 0)),
3100 label_text
get_desc (bool can_colorize
) const final override
3102 return make_label_text (can_colorize
,
3104 " is marked with %<__attribute__((tainted_args))%>",
3105 m_field
, DECL_CONTEXT (m_field
));
3112 /* Custom event for use by tainted_call_info when a callback field has been
3113 marked with __attribute__((tainted_args)), for labelling the function used
3114 in that callback. */
3116 class tainted_args_callback_custom_event
: public custom_event
3119 tainted_args_callback_custom_event (const event_loc_info
&loc_info
,
3121 : custom_event (loc_info
),
3126 label_text
get_desc (bool can_colorize
) const final override
3128 return make_label_text (can_colorize
,
3129 "function %qE used as initializer for field %qE"
3130 " marked with %<__attribute__((tainted_args))%>",
3131 get_fndecl (), m_field
);
3138 /* Custom edge info for use when adding a function used by a callback field
3139 marked with '__attribute__((tainted_args))'. */
3141 class tainted_args_call_info
: public custom_edge_info
3144 tainted_args_call_info (tree field
, tree fndecl
, location_t loc
)
3145 : m_field (field
), m_fndecl (fndecl
), m_loc (loc
)
3148 void print (pretty_printer
*pp
) const final override
3150 pp_string (pp
, "call to tainted field");
3153 bool update_model (region_model
*,
3154 const exploded_edge
*,
3155 region_model_context
*) const final override
3161 void add_events_to_path (checker_path
*emission_path
,
3162 const exploded_edge
&) const final override
3164 /* Show the field in the struct declaration, e.g.
3165 "(1) field 'store' is marked with '__attribute__((tainted_args))'" */
3166 emission_path
->add_event
3167 (make_unique
<tainted_args_field_custom_event
> (m_field
));
3169 /* Show the callback in the initializer
3171 "(2) function 'gadget_dev_desc_UDC_store' used as initializer
3172 for field 'store' marked with '__attribute__((tainted_args))'". */
3173 emission_path
->add_event
3174 (make_unique
<tainted_args_callback_custom_event
>
3175 (event_loc_info (m_loc
, m_fndecl
, 0),
3185 /* Given an initializer at LOC for FIELD marked with
3186 '__attribute__((tainted_args))' initialized with FNDECL, add an
3187 entrypoint to FNDECL to EG (and to its worklist) where the params to
3188 FNDECL are marked as tainted. */
3191 add_tainted_args_callback (exploded_graph
*eg
, tree field
, tree fndecl
,
3194 logger
*logger
= eg
->get_logger ();
3198 if (!gimple_has_body_p (fndecl
))
3201 const extrinsic_state
&ext_state
= eg
->get_ext_state ();
3203 function
*fun
= DECL_STRUCT_FUNCTION (fndecl
);
3207 = program_point::from_function_entry (*ext_state
.get_model_manager (),
3208 eg
->get_supergraph (), fun
);
3209 program_state
state (ext_state
);
3210 state
.push_frame (ext_state
, fun
);
3212 if (!mark_params_as_tainted (&state
, fndecl
, ext_state
))
3218 exploded_node
*enode
= eg
->get_or_create_node (point
, state
, NULL
);
3222 logger
->log ("created EN %i for tainted_args %qE entrypoint",
3223 enode
->m_index
, fndecl
);
3226 logger
->log ("did not create enode for tainted_args %qE entrypoint",
3232 eg
->add_edge (eg
->get_origin (), enode
, NULL
,
3233 make_unique
<tainted_args_call_info
> (field
, fndecl
, loc
));
3236 /* Callback for walk_tree for finding callbacks within initializers;
3237 ensure that any callback initializer where the corresponding field is
3238 marked with '__attribute__((tainted_args))' is treated as an entrypoint
3239 to the analysis, special-casing that the inputs to the callback are
3243 add_any_callbacks (tree
*tp
, int *, void *data
)
3245 exploded_graph
*eg
= (exploded_graph
*)data
;
3246 if (TREE_CODE (*tp
) == CONSTRUCTOR
)
3248 /* Find fields with the "tainted_args" attribute.
3249 walk_tree only walks the values, not the index values;
3250 look at the index values. */
3251 unsigned HOST_WIDE_INT idx
;
3252 constructor_elt
*ce
;
3254 for (idx
= 0; vec_safe_iterate (CONSTRUCTOR_ELTS (*tp
), idx
, &ce
);
3256 if (ce
->index
&& TREE_CODE (ce
->index
) == FIELD_DECL
)
3257 if (lookup_attribute ("tainted_args", DECL_ATTRIBUTES (ce
->index
)))
3259 tree value
= ce
->value
;
3260 if (TREE_CODE (value
) == ADDR_EXPR
3261 && TREE_CODE (TREE_OPERAND (value
, 0)) == FUNCTION_DECL
)
3262 add_tainted_args_callback (eg
, ce
->index
,
3263 TREE_OPERAND (value
, 0),
3264 EXPR_LOCATION (value
));
3271 /* Add initial nodes to EG, with entrypoints for externally-callable
3275 exploded_graph::build_initial_worklist ()
3277 logger
* const logger
= get_logger ();
3281 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
3283 function
*fun
= node
->get_fun ();
3284 if (!toplevel_function_p (fun
, logger
))
3286 exploded_node
*enode
= add_function_entry (fun
);
3290 logger
->log ("created EN %i for %qE entrypoint",
3291 enode
->m_index
, fun
->decl
);
3293 logger
->log ("did not create enode for %qE entrypoint", fun
->decl
);
3297 /* Find callbacks that are reachable from global initializers. */
3298 varpool_node
*vpnode
;
3299 FOR_EACH_VARIABLE (vpnode
)
3301 tree decl
= vpnode
->decl
;
3302 tree init
= DECL_INITIAL (decl
);
3305 walk_tree (&init
, add_any_callbacks
, this, NULL
);
3309 /* The main loop of the analysis.
3310 Take freshly-created exploded_nodes from the worklist, calling
3311 process_node on them to explore the <point, state> graph.
3312 Add edges to their successors, potentially creating new successors
3313 (which are also added to the worklist). */
3316 exploded_graph::process_worklist ()
3318 logger
* const logger
= get_logger ();
3320 auto_timevar
tv (TV_ANALYZER_WORKLIST
);
3322 while (m_worklist
.length () > 0)
3324 exploded_node
*node
= m_worklist
.take_next ();
3325 gcc_assert (node
->get_status () == exploded_node::STATUS_WORKLIST
);
3326 gcc_assert (node
->m_succs
.length () == 0
3327 || node
== m_origin
);
3330 logger
->log ("next to process: EN: %i", node
->m_index
);
3332 /* If we have a run of nodes that are before-supernode, try merging and
3333 processing them together, rather than pairwise or individually. */
3334 if (flag_analyzer_state_merge
&& node
!= m_origin
)
3335 if (maybe_process_run_of_before_supernode_enodes (node
))
3338 /* Avoid exponential explosions of nodes by attempting to merge
3339 nodes that are at the same program point and which have
3340 sufficiently similar state. */
3341 if (flag_analyzer_state_merge
&& node
!= m_origin
)
3342 if (exploded_node
*node_2
= m_worklist
.peek_next ())
3344 gcc_assert (node_2
->get_status ()
3345 == exploded_node::STATUS_WORKLIST
);
3346 gcc_assert (node
->m_succs
.length () == 0);
3347 gcc_assert (node_2
->m_succs
.length () == 0);
3349 gcc_assert (node
!= node_2
);
3352 logger
->log ("peek worklist: EN: %i", node_2
->m_index
);
3354 if (node
->get_point () == node_2
->get_point ())
3356 const program_point
&point
= node
->get_point ();
3360 pretty_printer
*pp
= logger
->get_printer ();
3361 logger
->start_log_line ();
3363 ("got potential merge EN: %i and EN: %i at ",
3364 node
->m_index
, node_2
->m_index
);
3365 point
.print (pp
, f
);
3366 logger
->end_log_line ();
3368 const program_state
&state
= node
->get_state ();
3369 const program_state
&state_2
= node_2
->get_state ();
3371 /* They shouldn't be equal, or we wouldn't have two
3373 gcc_assert (state
!= state_2
);
3375 program_state
merged_state (m_ext_state
);
3376 if (state
.can_merge_with_p (state_2
, m_ext_state
,
3377 point
, &merged_state
))
3380 logger
->log ("merging EN: %i and EN: %i",
3381 node
->m_index
, node_2
->m_index
);
3383 if (merged_state
== state
)
3385 /* Then merge node_2 into node by adding an edge. */
3386 add_edge (node_2
, node
, NULL
);
3388 /* Remove node_2 from the worklist. */
3389 m_worklist
.take_next ();
3390 node_2
->set_status (exploded_node::STATUS_MERGER
);
3392 /* Continue processing "node" below. */
3394 else if (merged_state
== state_2
)
3396 /* Then merge node into node_2, and leave node_2
3397 in the worklist, to be processed on the next
3399 add_edge (node
, node_2
, NULL
);
3400 node
->set_status (exploded_node::STATUS_MERGER
);
3405 /* We have a merged state that differs from
3406 both state and state_2. */
3408 /* Remove node_2 from the worklist. */
3409 m_worklist
.take_next ();
3411 /* Create (or get) an exploded node for the merged
3412 states, adding to the worklist. */
3413 exploded_node
*merged_enode
3414 = get_or_create_node (node
->get_point (),
3415 merged_state
, node
);
3416 if (merged_enode
== NULL
)
3420 logger
->log ("merged EN: %i and EN: %i into EN: %i",
3421 node
->m_index
, node_2
->m_index
,
3422 merged_enode
->m_index
);
3424 /* "node" and "node_2" have both now been removed
3425 from the worklist; we should not process them.
3427 "merged_enode" may be a new node; if so it will be
3428 processed in a subsequent iteration.
3429 Alternatively, "merged_enode" could be an existing
3430 node; one way the latter can
3431 happen is if we end up merging a succession of
3432 similar nodes into one. */
3434 /* If merged_node is one of the two we were merging,
3435 add it back to the worklist to ensure it gets
3438 Add edges from the merged nodes to it (but not a
3440 if (merged_enode
== node
)
3441 m_worklist
.add_node (merged_enode
);
3444 add_edge (node
, merged_enode
, NULL
);
3445 node
->set_status (exploded_node::STATUS_MERGER
);
3448 if (merged_enode
== node_2
)
3449 m_worklist
.add_node (merged_enode
);
3452 add_edge (node_2
, merged_enode
, NULL
);
3453 node_2
->set_status (exploded_node::STATUS_MERGER
);
3460 /* TODO: should we attempt more than two nodes,
3461 or just do pairs of nodes? (and hope that we get
3462 a cascade of mergers). */
3466 process_node (node
);
3469 /* Impose a hard limit on the number of exploded nodes, to ensure
3470 that the analysis terminates in the face of pathological state
3471 explosion (or bugs).
3473 Specifically, the limit is on the number of PK_AFTER_SUPERNODE
3474 exploded nodes, looking at supernode exit events.
3476 We use exit rather than entry since there can be multiple
3477 entry ENs, one per phi; the number of PK_AFTER_SUPERNODE ought
3478 to be equivalent to the number of supernodes multiplied by the
3479 number of states. */
3480 const int limit
= m_sg
.num_nodes () * param_analyzer_bb_explosion_factor
;
3481 if (m_global_stats
.m_num_nodes
[PK_AFTER_SUPERNODE
] > limit
)
3484 logger
->log ("bailing out; too many nodes");
3485 warning_at (node
->get_point ().get_location (),
3486 OPT_Wanalyzer_too_complex
,
3487 "analysis bailed out early"
3488 " (%i 'after-snode' enodes; %i enodes)",
3489 m_global_stats
.m_num_nodes
[PK_AFTER_SUPERNODE
],
3496 /* Attempt to process a consecutive run of sufficiently-similar nodes in
3497 the worklist at a CFG join-point (having already popped ENODE from the
3498 head of the worklist).
3500 If ENODE's point is of the form (before-supernode, SNODE) and the next
3501 nodes in the worklist are a consecutive run of enodes of the same form,
3502 for the same supernode as ENODE (but potentially from different in-edges),
3503 process them all together, setting their status to STATUS_BULK_MERGED,
3505 Otherwise, return false, in which case ENODE must be processed in the
3508 When processing them all together, generate successor states based
3509 on phi nodes for the appropriate CFG edges, and then attempt to merge
3510 these states into a minimal set of merged successor states, partitioning
3511 the inputs by merged successor state.
3513 Create new exploded nodes for all of the merged states, and add edges
3514 connecting the input enodes to the corresponding merger exploded nodes.
3516 We hope we have a much smaller number of merged successor states
3517 compared to the number of input enodes - ideally just one,
3518 if all successor states can be merged.
3520 Processing and merging many together as one operation rather than as
3521 pairs avoids scaling issues where per-pair mergers could bloat the
3522 graph with merger nodes (especially so after switch statements). */
3526 maybe_process_run_of_before_supernode_enodes (exploded_node
*enode
)
3528 /* A struct for tracking per-input state. */
3531 item (exploded_node
*input_enode
)
3532 : m_input_enode (input_enode
),
3533 m_processed_state (input_enode
->get_state ()),
3537 exploded_node
*m_input_enode
;
3538 program_state m_processed_state
;
3542 gcc_assert (enode
->get_status () == exploded_node::STATUS_WORKLIST
);
3543 gcc_assert (enode
->m_succs
.length () == 0);
3545 const program_point
&point
= enode
->get_point ();
3547 if (point
.get_kind () != PK_BEFORE_SUPERNODE
)
3550 const supernode
*snode
= point
.get_supernode ();
3552 logger
* const logger
= get_logger ();
3555 /* Find a run of enodes in the worklist that are before the same supernode,
3556 but potentially from different in-edges. */
3557 auto_vec
<exploded_node
*> enodes
;
3558 enodes
.safe_push (enode
);
3559 while (exploded_node
*enode_2
= m_worklist
.peek_next ())
3561 gcc_assert (enode_2
->get_status ()
3562 == exploded_node::STATUS_WORKLIST
);
3563 gcc_assert (enode_2
->m_succs
.length () == 0);
3565 const program_point
&point_2
= enode_2
->get_point ();
3567 if (point_2
.get_kind () == PK_BEFORE_SUPERNODE
3568 && point_2
.get_supernode () == snode
3569 && &point_2
.get_call_string () == &point
.get_call_string ())
3571 enodes
.safe_push (enode_2
);
3572 m_worklist
.take_next ();
3578 /* If the only node is ENODE, then give up. */
3579 if (enodes
.length () == 1)
3583 logger
->log ("got run of %i enodes for SN: %i",
3584 enodes
.length (), snode
->m_index
);
3586 /* All of these enodes have a shared successor point (even if they
3587 were for different in-edges). */
3588 program_point
next_point (point
.get_next ());
3590 /* Calculate the successor state for each enode in enodes. */
3591 auto_delete_vec
<item
> items (enodes
.length ());
3593 exploded_node
*iter_enode
;
3594 FOR_EACH_VEC_ELT (enodes
, i
, iter_enode
)
3596 item
*it
= new item (iter_enode
);
3597 items
.quick_push (it
);
3598 const program_state
&state
= iter_enode
->get_state ();
3599 program_state
*next_state
= &it
->m_processed_state
;
3600 next_state
->validate (m_ext_state
);
3601 const program_point
&iter_point
= iter_enode
->get_point ();
3602 if (const superedge
*iter_sedge
= iter_point
.get_from_edge ())
3604 uncertainty_t uncertainty
;
3605 impl_region_model_context
ctxt (*this, iter_enode
,
3607 &uncertainty
, NULL
, NULL
);
3608 const cfg_superedge
*last_cfg_superedge
3609 = iter_sedge
->dyn_cast_cfg_superedge ();
3610 if (last_cfg_superedge
)
3611 next_state
->m_region_model
->update_for_phis
3612 (snode
, last_cfg_superedge
, &ctxt
);
3614 next_state
->validate (m_ext_state
);
3617 /* Attempt to partition the items into a set of merged states.
3618 We hope we have a much smaller number of merged states
3619 compared to the number of input enodes - ideally just one,
3620 if all can be merged. */
3621 auto_delete_vec
<program_state
> merged_states
;
3622 auto_vec
<item
*> first_item_for_each_merged_state
;
3624 FOR_EACH_VEC_ELT (items
, i
, it
)
3626 const program_state
&it_state
= it
->m_processed_state
;
3627 program_state
*merged_state
;
3628 unsigned iter_merger_idx
;
3629 FOR_EACH_VEC_ELT (merged_states
, iter_merger_idx
, merged_state
)
3631 merged_state
->validate (m_ext_state
);
3632 program_state
merge (m_ext_state
);
3633 if (it_state
.can_merge_with_p (*merged_state
, m_ext_state
,
3634 next_point
, &merge
))
3636 *merged_state
= merge
;
3637 merged_state
->validate (m_ext_state
);
3638 it
->m_merger_idx
= iter_merger_idx
;
3640 logger
->log ("reusing merger state %i for item %i (EN: %i)",
3641 it
->m_merger_idx
, i
, it
->m_input_enode
->m_index
);
3645 /* If it couldn't be merged with any existing merged_states,
3646 create a new one. */
3647 if (it
->m_merger_idx
== -1)
3649 it
->m_merger_idx
= merged_states
.length ();
3650 merged_states
.safe_push (new program_state (it_state
));
3651 first_item_for_each_merged_state
.safe_push (it
);
3653 logger
->log ("using new merger state %i for item %i (EN: %i)",
3654 it
->m_merger_idx
, i
, it
->m_input_enode
->m_index
);
3657 gcc_assert (it
->m_merger_idx
>= 0);
3658 gcc_assert ((unsigned)it
->m_merger_idx
< merged_states
.length ());
3661 /* Create merger nodes. */
3662 auto_vec
<exploded_node
*> next_enodes (merged_states
.length ());
3663 program_state
*merged_state
;
3664 FOR_EACH_VEC_ELT (merged_states
, i
, merged_state
)
3666 exploded_node
*src_enode
3667 = first_item_for_each_merged_state
[i
]->m_input_enode
;
3669 = get_or_create_node (next_point
, *merged_state
, src_enode
);
3670 /* "next" could be NULL; we handle that when adding the edges below. */
3671 next_enodes
.quick_push (next
);
3675 logger
->log ("using EN: %i for merger state %i", next
->m_index
, i
);
3677 logger
->log ("using NULL enode for merger state %i", i
);
3681 /* Create edges from each input enode to the appropriate successor enode.
3682 Update the status of the now-processed input enodes. */
3683 FOR_EACH_VEC_ELT (items
, i
, it
)
3685 exploded_node
*next
= next_enodes
[it
->m_merger_idx
];
3687 add_edge (it
->m_input_enode
, next
, NULL
);
3688 it
->m_input_enode
->set_status (exploded_node::STATUS_BULK_MERGED
);
3692 logger
->log ("merged %i in-enodes into %i out-enode(s) at SN: %i",
3693 items
.length (), merged_states
.length (), snode
->m_index
);
3698 /* Return true if STMT must appear at the start of its exploded node, and
3699 thus we can't consolidate its effects within a run of other statements,
3700 where PREV_STMT was the previous statement. */
3703 stmt_requires_new_enode_p (const gimple
*stmt
,
3704 const gimple
*prev_stmt
)
3706 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
3708 /* Stop consolidating at calls to
3709 "__analyzer_dump_exploded_nodes", so they always appear at the
3710 start of an exploded_node. */
3711 if (is_special_named_call_p (call
, "__analyzer_dump_exploded_nodes",
3715 /* sm-signal.cc injects an additional custom eedge at "signal" calls
3716 from the registration enode to the handler enode, separate from the
3717 regular next state, which defeats the "detect state change" logic
3718 in process_node. Work around this via special-casing, to ensure
3719 we split the enode immediately before any "signal" call. */
3720 if (is_special_named_call_p (call
, "signal", 2))
3724 /* If we had a PREV_STMT with an unknown location, and this stmt
3725 has a known location, then if a state change happens here, it
3726 could be consolidated into PREV_STMT, giving us an event with
3727 no location. Ensure that STMT gets its own exploded_node to
3729 if (get_pure_location (prev_stmt
->location
) == UNKNOWN_LOCATION
3730 && get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
3736 /* Return true if OLD_STATE and NEW_STATE are sufficiently different that
3737 we should split enodes and create an exploded_edge separating them
3738 (which makes it easier to identify state changes of intereset when
3739 constructing checker_paths). */
3742 state_change_requires_new_enode_p (const program_state
&old_state
,
3743 const program_state
&new_state
)
3745 /* Changes in dynamic extents signify creations of heap/alloca regions
3746 and resizings of heap regions; likely to be of interest in
3747 diagnostic paths. */
3748 if (old_state
.m_region_model
->get_dynamic_extents ()
3749 != new_state
.m_region_model
->get_dynamic_extents ())
3752 /* Changes in sm-state are of interest. */
3755 FOR_EACH_VEC_ELT (old_state
.m_checker_states
, sm_idx
, smap
)
3757 const sm_state_map
*old_smap
= old_state
.m_checker_states
[sm_idx
];
3758 const sm_state_map
*new_smap
= new_state
.m_checker_states
[sm_idx
];
3759 if (*old_smap
!= *new_smap
)
3766 /* Create enodes and eedges for the function calls that doesn't have an
3767 underlying call superedge.
3769 Such case occurs when GCC's middle end didn't know which function to
3770 call but the analyzer does (with the help of current state).
3772 Some example such calls are dynamically dispatched calls to virtual
3773 functions or calls that happen via function pointer. */
3776 exploded_graph::maybe_create_dynamic_call (const gcall
*call
,
3778 exploded_node
*node
,
3779 program_state next_state
,
3780 program_point
&next_point
,
3781 uncertainty_t
*uncertainty
,
3786 const program_point
*this_point
= &node
->get_point ();
3787 function
*fun
= DECL_STRUCT_FUNCTION (fn_decl
);
3790 const supergraph
&sg
= this->get_supergraph ();
3791 supernode
*sn_entry
= sg
.get_node_for_function_entry (fun
);
3792 supernode
*sn_exit
= sg
.get_node_for_function_exit (fun
);
3794 program_point new_point
3795 = program_point::before_supernode (sn_entry
,
3797 this_point
->get_call_string ());
3799 new_point
.push_to_call_stack (sn_exit
,
3800 next_point
.get_supernode());
3802 /* Impose a maximum recursion depth and don't analyze paths
3803 that exceed it further.
3804 This is something of a blunt workaround, but it only
3805 applies to recursion (and mutual recursion), not to
3806 general call stacks. */
3807 if (new_point
.get_call_string ().calc_recursion_depth ()
3808 > param_analyzer_max_recursion_depth
)
3811 logger
->log ("rejecting call edge: recursion limit exceeded");
3815 next_state
.push_call (*this, node
, call
, uncertainty
);
3817 if (next_state
.m_valid
)
3820 logger
->log ("Discovered call to %s [SN: %i -> SN: %i]",
3822 this_point
->get_supernode ()->m_index
,
3825 exploded_node
*enode
= get_or_create_node (new_point
,
3829 add_edge (node
,enode
, NULL
,
3830 make_unique
<dynamic_call_info_t
> (call
));
3837 /* Subclass of path_context for use within exploded_graph::process_node,
3838 so that we can split states e.g. at "realloc" calls. */
3840 class impl_path_context
: public path_context
3843 impl_path_context (const program_state
*cur_state
)
3844 : m_cur_state (cur_state
),
3845 m_terminate_path (false)
3849 bool bifurcation_p () const
3851 return m_custom_eedge_infos
.length () > 0;
3854 const program_state
&get_state_at_bifurcation () const
3856 gcc_assert (m_state_at_bifurcation
);
3857 return *m_state_at_bifurcation
;
3861 bifurcate (std::unique_ptr
<custom_edge_info
> info
) final override
3863 if (m_state_at_bifurcation
)
3864 /* Verify that the state at bifurcation is consistent when we
3865 split into multiple out-edges. */
3866 gcc_assert (*m_state_at_bifurcation
== *m_cur_state
);
3868 /* Take a copy of the cur_state at the moment when bifurcation
3870 m_state_at_bifurcation
3871 = std::unique_ptr
<program_state
> (new program_state (*m_cur_state
));
3873 /* Take ownership of INFO. */
3874 m_custom_eedge_infos
.safe_push (info
.release ());
3877 void terminate_path () final override
3879 m_terminate_path
= true;
3882 bool terminate_path_p () const final override
3884 return m_terminate_path
;
3887 const vec
<custom_edge_info
*> & get_custom_eedge_infos ()
3889 return m_custom_eedge_infos
;
3893 const program_state
*m_cur_state
;
3895 /* Lazily-created copy of the state before the split. */
3896 std::unique_ptr
<program_state
> m_state_at_bifurcation
;
3898 auto_vec
<custom_edge_info
*> m_custom_eedge_infos
;
3900 bool m_terminate_path
;
3903 /* A subclass of pending_diagnostic for complaining about jumps through NULL
3904 function pointers. */
3906 class jump_through_null
: public pending_diagnostic_subclass
<jump_through_null
>
3909 jump_through_null (const gcall
*call
)
3913 const char *get_kind () const final override
3915 return "jump_through_null";
3918 bool operator== (const jump_through_null
&other
) const
3920 return m_call
== other
.m_call
;
3923 int get_controlling_option () const final override
3925 return OPT_Wanalyzer_jump_through_null
;
3928 bool emit (rich_location
*rich_loc
, logger
*) final override
3930 return warning_at (rich_loc
, get_controlling_option (),
3931 "jump through null pointer");
3934 label_text
describe_final_event (const evdesc::final_event
&ev
) final override
3936 return ev
.formatted_print ("jump through null pointer here");
3940 const gcall
*m_call
;
3943 /* The core of exploded_graph::process_worklist (the main analysis loop),
3944 handling one node in the worklist.
3946 Get successor <point, state> pairs for NODE, calling get_or_create on
3947 them, and adding an exploded_edge to each successors.
3949 Freshly-created nodes will be added to the worklist. */
3952 exploded_graph::process_node (exploded_node
*node
)
3954 logger
* const logger
= get_logger ();
3955 LOG_FUNC_1 (logger
, "EN: %i", node
->m_index
);
3957 node
->set_status (exploded_node::STATUS_PROCESSED
);
3959 const program_point
&point
= node
->get_point ();
3961 /* Update cfun and input_location in case of an ICE: make it easier to
3962 track down which source construct we're failing to handle. */
3963 auto_cfun
sentinel (node
->get_function ());
3964 const gimple
*stmt
= point
.get_stmt ();
3966 input_location
= stmt
->location
;
3968 const program_state
&state
= node
->get_state ();
3971 pretty_printer
*pp
= logger
->get_printer ();
3972 logger
->start_log_line ();
3973 pp_string (pp
, "point: ");
3974 point
.print (pp
, format (false));
3975 pp_string (pp
, ", state: ");
3976 state
.dump_to_pp (m_ext_state
, true, false, pp
);
3977 logger
->end_log_line ();
3980 switch (point
.get_kind ())
3985 /* This node exists to simplify finding the shortest path
3986 to an exploded_node. */
3989 case PK_BEFORE_SUPERNODE
:
3991 program_state
next_state (state
);
3992 uncertainty_t uncertainty
;
3994 if (point
.get_from_edge ())
3996 impl_region_model_context
ctxt (*this, node
,
3997 &state
, &next_state
,
3998 &uncertainty
, NULL
, NULL
);
3999 const cfg_superedge
*last_cfg_superedge
4000 = point
.get_from_edge ()->dyn_cast_cfg_superedge ();
4001 if (last_cfg_superedge
)
4002 next_state
.m_region_model
->update_for_phis
4003 (node
->get_supernode (),
4006 program_state::detect_leaks (state
, next_state
, NULL
,
4007 get_ext_state (), &ctxt
);
4010 program_point
next_point (point
.get_next ());
4011 exploded_node
*next
= get_or_create_node (next_point
, next_state
, node
);
4013 add_edge (node
, next
, NULL
);
4016 case PK_BEFORE_STMT
:
4018 /* Determine the effect of a run of one or more statements
4019 within one supernode, generating an edge to the program_point
4020 after the last statement that's processed.
4022 Stop iterating statements and thus consolidating into one enode
4024 - reaching the end of the statements in the supernode
4025 - if an sm-state-change occurs (so that it gets its own
4027 - if "-fanalyzer-fine-grained" is active
4028 - encountering certain statements must appear at the start of
4029 their enode (for which stmt_requires_new_enode_p returns true)
4031 Update next_state in-place, to get the result of the one
4032 or more stmts that are processed.
4034 Split the node in-place if an sm-state-change occurs, so that
4035 the sm-state-change occurs on an edge where the src enode has
4036 exactly one stmt, the one that caused the change. */
4037 program_state
next_state (state
);
4039 impl_path_context
path_ctxt (&next_state
);
4041 uncertainty_t uncertainty
;
4042 const supernode
*snode
= point
.get_supernode ();
4044 const gimple
*prev_stmt
= NULL
;
4045 for (stmt_idx
= point
.get_stmt_idx ();
4046 stmt_idx
< snode
->m_stmts
.length ();
4049 const gimple
*stmt
= snode
->m_stmts
[stmt_idx
];
4051 if (stmt_idx
> point
.get_stmt_idx ())
4052 if (stmt_requires_new_enode_p (stmt
, prev_stmt
))
4059 program_state
old_state (next_state
);
4061 /* Process the stmt. */
4062 exploded_node::on_stmt_flags flags
4063 = node
->on_stmt (*this, snode
, stmt
, &next_state
, &uncertainty
,
4065 node
->m_num_processed_stmts
++;
4067 /* If flags.m_terminate_path, stop analyzing; any nodes/edges
4068 will have been added by on_stmt (e.g. for handling longjmp). */
4069 if (flags
.m_terminate_path
)
4072 if (next_state
.m_region_model
)
4074 impl_region_model_context
ctxt (*this, node
,
4075 &old_state
, &next_state
,
4076 &uncertainty
, NULL
, stmt
);
4077 program_state::detect_leaks (old_state
, next_state
, NULL
,
4078 get_ext_state (), &ctxt
);
4081 unsigned next_idx
= stmt_idx
+ 1;
4082 program_point next_point
4083 = (next_idx
< point
.get_supernode ()->m_stmts
.length ()
4084 ? program_point::before_stmt (point
.get_supernode (), next_idx
,
4085 point
.get_call_string ())
4086 : program_point::after_supernode (point
.get_supernode (),
4087 point
.get_call_string ()));
4088 next_state
= next_state
.prune_for_point (*this, next_point
, node
,
4091 if (flag_analyzer_fine_grained
4092 || state_change_requires_new_enode_p (old_state
, next_state
)
4093 || path_ctxt
.bifurcation_p ()
4094 || path_ctxt
.terminate_path_p ())
4096 program_point split_point
4097 = program_point::before_stmt (point
.get_supernode (),
4099 point
.get_call_string ());
4100 if (split_point
!= node
->get_point ())
4102 /* If we're not at the start of NODE, split the enode at
4103 this stmt, so we have:
4105 so that when split_enode is processed the next edge
4108 and any state change will effectively occur on that
4109 latter edge, and split_enode will contain just stmt. */
4111 logger
->log ("getting split_enode");
4112 exploded_node
*split_enode
4113 = get_or_create_node (split_point
, old_state
, node
);
4116 /* "stmt" will be reprocessed when split_enode is
4118 node
->m_num_processed_stmts
--;
4120 logger
->log ("creating edge to split_enode");
4121 add_edge (node
, split_enode
, NULL
);
4125 /* If we're at the start of NODE, stop iterating,
4126 so that an edge will be created from NODE to
4127 (next_point, next_state) below. */
4131 unsigned next_idx
= stmt_idx
+ 1;
4132 program_point next_point
4133 = (next_idx
< point
.get_supernode ()->m_stmts
.length ()
4134 ? program_point::before_stmt (point
.get_supernode (), next_idx
,
4135 point
.get_call_string ())
4136 : program_point::after_supernode (point
.get_supernode (),
4137 point
.get_call_string ()));
4138 if (path_ctxt
.terminate_path_p ())
4141 logger
->log ("not adding node: terminating path");
4146 = get_or_create_node (next_point
, next_state
, node
);
4148 add_edge (node
, next
, NULL
);
4151 /* If we have custom edge infos, "bifurcate" the state
4152 accordingly, potentially creating a new state/enode/eedge
4153 instances. For example, to handle a "realloc" call, we
4154 might split into 3 states, for the "failure",
4155 "resizing in place", and "moving to a new buffer" cases. */
4156 for (auto edge_info_iter
: path_ctxt
.get_custom_eedge_infos ())
4158 /* Take ownership of the edge infos from the path_ctxt. */
4159 std::unique_ptr
<custom_edge_info
> edge_info (edge_info_iter
);
4162 logger
->start_log_line ();
4163 logger
->log_partial ("bifurcating for edge: ");
4164 edge_info
->print (logger
->get_printer ());
4165 logger
->end_log_line ();
4167 program_state bifurcated_new_state
4168 (path_ctxt
.get_state_at_bifurcation ());
4170 /* Apply edge_info to state. */
4171 impl_region_model_context
4172 bifurcation_ctxt (*this,
4173 node
, // enode_for_diag
4174 &path_ctxt
.get_state_at_bifurcation (),
4175 &bifurcated_new_state
,
4176 NULL
, // uncertainty_t *uncertainty
4177 NULL
, // path_context *path_ctxt
4179 if (edge_info
->update_state (&bifurcated_new_state
,
4180 NULL
, /* no exploded_edge yet. */
4183 exploded_node
*next2
4184 = get_or_create_node (next_point
, bifurcated_new_state
, node
);
4186 add_edge (node
, next2
, NULL
, std::move (edge_info
));
4191 logger
->log ("infeasible state, not adding node");
4196 case PK_AFTER_SUPERNODE
:
4198 bool found_a_superedge
= false;
4199 bool is_an_exit_block
= false;
4200 /* If this is an EXIT BB, detect leaks, and potentially
4201 create a function summary. */
4202 if (point
.get_supernode ()->return_p ())
4204 is_an_exit_block
= true;
4205 node
->detect_leaks (*this);
4206 if (flag_analyzer_call_summaries
4207 && point
.get_call_string ().empty_p ())
4209 /* TODO: create function summary
4210 There can be more than one; each corresponds to a different
4211 final enode in the function. */
4214 pretty_printer
*pp
= logger
->get_printer ();
4215 logger
->start_log_line ();
4217 ("would create function summary for %qE; state: ",
4218 point
.get_fndecl ());
4219 state
.dump_to_pp (m_ext_state
, true, false, pp
);
4220 logger
->end_log_line ();
4222 per_function_data
*per_fn_data
4223 = get_or_create_per_function_data (point
.get_function ());
4224 per_fn_data
->add_call_summary (node
);
4227 /* Traverse into successors of the supernode. */
4230 FOR_EACH_VEC_ELT (point
.get_supernode ()->m_succs
, i
, succ
)
4232 found_a_superedge
= true;
4235 label_text
succ_desc (succ
->get_description (false));
4236 logger
->log ("considering SN: %i -> SN: %i (%s)",
4237 succ
->m_src
->m_index
, succ
->m_dest
->m_index
,
4241 program_point next_point
4242 = program_point::before_supernode (succ
->m_dest
, succ
,
4243 point
.get_call_string ());
4244 program_state
next_state (state
);
4245 uncertainty_t uncertainty
;
4247 /* Make use the current state and try to discover and analyse
4248 indirect function calls (a call that doesn't have an underlying
4249 cgraph edge representing call).
4251 Some examples of such calls are virtual function calls
4252 and calls that happen via a function pointer. */
4253 if (succ
->m_kind
== SUPEREDGE_INTRAPROCEDURAL_CALL
4254 && !(succ
->get_any_callgraph_edge ()))
4257 = point
.get_supernode ()->get_final_call ();
4259 impl_region_model_context
ctxt (*this,
4267 region_model
*model
= state
.m_region_model
;
4268 bool call_discovered
= false;
4270 if (tree fn_decl
= model
->get_fndecl_for_call (call
, &ctxt
))
4271 call_discovered
= maybe_create_dynamic_call (call
,
4278 if (!call_discovered
)
4280 /* Check for jump through NULL. */
4281 if (tree fn_ptr
= gimple_call_fn (call
))
4283 const svalue
*fn_ptr_sval
4284 = model
->get_rvalue (fn_ptr
, &ctxt
);
4285 if (fn_ptr_sval
->all_zeroes_p ())
4286 ctxt
.warn (make_unique
<jump_through_null
> (call
));
4289 /* An unknown function or a special function was called
4290 at this point, in such case, don't terminate the
4291 analysis of the current function.
4293 The analyzer handles calls to such functions while
4294 analysing the stmt itself, so the function call
4295 must have been handled by the anlyzer till now. */
4297 = get_or_create_node (next_point
,
4301 add_edge (node
, next
, succ
);
4305 if (!node
->on_edge (*this, succ
, &next_point
, &next_state
,
4309 logger
->log ("skipping impossible edge to SN: %i",
4310 succ
->m_dest
->m_index
);
4313 exploded_node
*next
= get_or_create_node (next_point
, next_state
,
4317 add_edge (node
, next
, succ
);
4319 /* We might have a function entrypoint. */
4320 detect_infinite_recursion (next
);
4324 /* Return from the calls which doesn't have a return superedge.
4325 Such case occurs when GCC's middle end didn't knew which function to
4326 call but analyzer did. */
4327 if ((is_an_exit_block
&& !found_a_superedge
)
4328 && (!point
.get_call_string ().empty_p ()))
4330 const call_string
&cs
= point
.get_call_string ();
4331 program_point next_point
4332 = program_point::before_supernode (cs
.get_caller_node (),
4335 program_state
next_state (state
);
4336 uncertainty_t uncertainty
;
4339 = next_point
.get_supernode ()->get_returning_call ();
4342 next_state
.returning_call (*this, node
, call
, &uncertainty
);
4344 if (next_state
.m_valid
)
4346 next_point
.pop_from_call_stack ();
4347 exploded_node
*enode
= get_or_create_node (next_point
,
4351 add_edge (node
, enode
, NULL
,
4352 make_unique
<dynamic_call_info_t
> (call
, true));
4360 /* Ensure that this graph has a stats instance for FN, return it.
4361 FN can be NULL, in which case a stats instances is returned covering
4362 "functionless" parts of the graph (the origin node). */
4365 exploded_graph::get_or_create_function_stats (function
*fn
)
4368 return &m_functionless_stats
;
4370 if (stats
**slot
= m_per_function_stats
.get (fn
))
4374 int num_supernodes
= fn
? n_basic_blocks_for_fn (fn
) : 0;
4375 /* not quite the num supernodes, but nearly. */
4376 stats
*new_stats
= new stats (num_supernodes
);
4377 m_per_function_stats
.put (fn
, new_stats
);
4382 /* Print bar charts to PP showing:
4383 - the number of enodes per function, and
4384 - for each function:
4385 - the number of enodes per supernode/BB
4386 - the number of excess enodes per supernode/BB beyond the
4387 per-program-point limit, if there were any. */
4390 exploded_graph::print_bar_charts (pretty_printer
*pp
) const
4392 cgraph_node
*cgnode
;
4394 pp_string (pp
, "enodes per function:");
4396 bar_chart enodes_per_function
;
4397 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode
)
4399 function
*fn
= cgnode
->get_fun ();
4400 const stats
* const *s_ptr
4401 = const_cast <function_stat_map_t
&> (m_per_function_stats
).get (fn
);
4402 enodes_per_function
.add_item (function_name (fn
),
4403 s_ptr
? (*s_ptr
)->get_total_enodes () : 0);
4405 enodes_per_function
.print (pp
);
4407 /* Accumulate number of enodes per supernode. */
4408 auto_vec
<unsigned> enodes_per_supernode (m_sg
.num_nodes ());
4409 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
4410 enodes_per_supernode
.quick_push (0);
4412 exploded_node
*enode
;
4413 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
4415 const supernode
*iter_snode
= enode
->get_supernode ();
4418 enodes_per_supernode
[iter_snode
->m_index
]++;
4421 /* Accumulate excess enodes per supernode. */
4422 auto_vec
<unsigned> excess_enodes_per_supernode (m_sg
.num_nodes ());
4423 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
4424 excess_enodes_per_supernode
.quick_push (0);
4425 for (point_map_t::iterator iter
= m_per_point_data
.begin ();
4426 iter
!= m_per_point_data
.end (); ++iter
)
4428 const program_point
*point
= (*iter
).first
;
4429 const supernode
*iter_snode
= point
->get_supernode ();
4432 const per_program_point_data
*point_data
= (*iter
).second
;
4433 excess_enodes_per_supernode
[iter_snode
->m_index
]
4434 += point_data
->m_excess_enodes
;
4437 /* Show per-function bar_charts of enodes per supernode/BB. */
4438 pp_string (pp
, "per-function enodes per supernode/BB:");
4440 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode
)
4442 function
*fn
= cgnode
->get_fun ();
4443 pp_printf (pp
, "function: %qs", function_name (fn
));
4446 bar_chart enodes_per_snode
;
4447 bar_chart excess_enodes_per_snode
;
4448 bool have_excess_enodes
= false;
4449 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
4451 const supernode
*iter_snode
= m_sg
.get_node_by_index (i
);
4452 if (iter_snode
->get_function () != fn
)
4454 pretty_printer tmp_pp
;
4455 pp_printf (&tmp_pp
, "sn %i (bb %i)",
4456 iter_snode
->m_index
, iter_snode
->m_bb
->index
);
4457 enodes_per_snode
.add_item (pp_formatted_text (&tmp_pp
),
4458 enodes_per_supernode
[iter_snode
->m_index
]);
4459 const int num_excess
4460 = excess_enodes_per_supernode
[iter_snode
->m_index
];
4461 excess_enodes_per_snode
.add_item (pp_formatted_text (&tmp_pp
),
4464 have_excess_enodes
= true;
4466 enodes_per_snode
.print (pp
);
4467 if (have_excess_enodes
)
4469 pp_printf (pp
, "EXCESS ENODES:");
4471 excess_enodes_per_snode
.print (pp
);
4476 /* Write all stats information to this graph's logger, if any. */
4479 exploded_graph::log_stats () const
4481 logger
* const logger
= get_logger ();
4487 m_ext_state
.get_engine ()->log_stats (logger
);
4489 logger
->log ("m_sg.num_nodes (): %i", m_sg
.num_nodes ());
4490 logger
->log ("m_nodes.length (): %i", m_nodes
.length ());
4491 logger
->log ("m_edges.length (): %i", m_edges
.length ());
4492 logger
->log ("remaining enodes in worklist: %i", m_worklist
.length ());
4494 logger
->log ("global stats:");
4495 m_global_stats
.log (logger
);
4497 for (function_stat_map_t::iterator iter
= m_per_function_stats
.begin ();
4498 iter
!= m_per_function_stats
.end ();
4501 function
*fn
= (*iter
).first
;
4502 log_scope
s (logger
, function_name (fn
));
4503 (*iter
).second
->log (logger
);
4506 print_bar_charts (logger
->get_printer ());
4509 /* Dump all stats information to OUT. */
4512 exploded_graph::dump_stats (FILE *out
) const
4514 fprintf (out
, "m_sg.num_nodes (): %i\n", m_sg
.num_nodes ());
4515 fprintf (out
, "m_nodes.length (): %i\n", m_nodes
.length ());
4516 fprintf (out
, "m_edges.length (): %i\n", m_edges
.length ());
4517 fprintf (out
, "remaining enodes in worklist: %i", m_worklist
.length ());
4519 fprintf (out
, "global stats:\n");
4520 m_global_stats
.dump (out
);
4522 for (function_stat_map_t::iterator iter
= m_per_function_stats
.begin ();
4523 iter
!= m_per_function_stats
.end ();
4526 function
*fn
= (*iter
).first
;
4527 fprintf (out
, "function: %s\n", function_name (fn
));
4528 (*iter
).second
->dump (out
);
4531 fprintf (out
, "PK_AFTER_SUPERNODE per supernode:\n");
4532 for (unsigned i
= 0; i
< m_PK_AFTER_SUPERNODE_per_snode
.length (); i
++)
4533 fprintf (out
, " SN %i: %3i\n", i
, m_PK_AFTER_SUPERNODE_per_snode
[i
]);
4537 exploded_graph::dump_states_for_supernode (FILE *out
,
4538 const supernode
*snode
) const
4540 fprintf (out
, "PK_AFTER_SUPERNODE nodes for SN: %i\n", snode
->m_index
);
4542 exploded_node
*enode
;
4544 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
4546 const supernode
*iter_snode
= enode
->get_supernode ();
4547 if (enode
->get_point ().get_kind () == PK_AFTER_SUPERNODE
4548 && iter_snode
== snode
)
4551 pp_format_decoder (&pp
) = default_tree_printer
;
4552 enode
->get_state ().dump_to_pp (m_ext_state
, true, false, &pp
);
4553 fprintf (out
, "state %i: EN: %i\n %s\n",
4554 state_idx
++, enode
->m_index
,
4555 pp_formatted_text (&pp
));
4558 fprintf (out
, "#exploded_node for PK_AFTER_SUPERNODE for SN: %i = %i\n",
4559 snode
->m_index
, state_idx
);
4562 /* Return a new json::object of the form
4563 {"nodes" : [objs for enodes],
4564 "edges" : [objs for eedges],
4565 "ext_state": object for extrinsic_state,
4566 "diagnostic_manager": object for diagnostic_manager}. */
4569 exploded_graph::to_json () const
4571 json::object
*egraph_obj
= new json::object ();
4575 json::array
*nodes_arr
= new json::array ();
4578 FOR_EACH_VEC_ELT (m_nodes
, i
, n
)
4579 nodes_arr
->append (n
->to_json (m_ext_state
));
4580 egraph_obj
->set ("nodes", nodes_arr
);
4585 json::array
*edges_arr
= new json::array ();
4588 FOR_EACH_VEC_ELT (m_edges
, i
, n
)
4589 edges_arr
->append (n
->to_json ());
4590 egraph_obj
->set ("edges", edges_arr
);
4593 /* m_sg is JSONified at the top-level. */
4595 egraph_obj
->set ("ext_state", m_ext_state
.to_json ());
4596 egraph_obj
->set ("worklist", m_worklist
.to_json ());
4597 egraph_obj
->set ("diagnostic_manager", m_diagnostic_manager
.to_json ());
4599 /* The following fields aren't yet being JSONified:
4600 const state_purge_map *const m_purge_map;
4601 const analysis_plan &m_plan;
4602 stats m_global_stats;
4603 function_stat_map_t m_per_function_stats;
4604 stats m_functionless_stats;
4605 call_string_data_map_t m_per_call_string_data;
4606 auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode; */
4611 /* class exploded_path. */
4615 exploded_path::exploded_path (const exploded_path
&other
)
4616 : m_edges (other
.m_edges
.length ())
4619 const exploded_edge
*eedge
;
4620 FOR_EACH_VEC_ELT (other
.m_edges
, i
, eedge
)
4621 m_edges
.quick_push (eedge
);
4624 /* Look for the last use of SEARCH_STMT within this path.
4625 If found write the edge's index to *OUT_IDX and return true, otherwise
4629 exploded_path::find_stmt_backwards (const gimple
*search_stmt
,
4633 const exploded_edge
*eedge
;
4634 FOR_EACH_VEC_ELT_REVERSE (m_edges
, i
, eedge
)
4636 const exploded_node
*dst_node
= eedge
->m_dest
;
4637 const program_point
&dst_point
= dst_node
->get_point ();
4638 const gimple
*stmt
= dst_point
.get_stmt ();
4639 if (stmt
== search_stmt
)
4648 /* Get the final exploded_node in this path, which must be non-empty. */
4651 exploded_path::get_final_enode () const
4653 gcc_assert (m_edges
.length () > 0);
4654 return m_edges
[m_edges
.length () - 1]->m_dest
;
4657 /* Check state along this path, returning true if it is feasible.
4658 If OUT is non-NULL, and the path is infeasible, write a new
4659 feasibility_problem to *OUT. */
4662 exploded_path::feasible_p (logger
*logger
,
4663 std::unique_ptr
<feasibility_problem
> *out
,
4664 engine
*eng
, const exploded_graph
*eg
) const
4668 feasibility_state
state (eng
->get_model_manager (),
4669 eg
->get_supergraph ());
4671 /* Traverse the path, updating this state. */
4672 for (unsigned edge_idx
= 0; edge_idx
< m_edges
.length (); edge_idx
++)
4674 const exploded_edge
*eedge
= m_edges
[edge_idx
];
4676 logger
->log ("considering edge %i: EN:%i -> EN:%i",
4678 eedge
->m_src
->m_index
,
4679 eedge
->m_dest
->m_index
);
4681 rejected_constraint
*rc
= NULL
;
4682 if (!state
.maybe_update_for_edge (logger
, eedge
, &rc
))
4687 const exploded_node
&src_enode
= *eedge
->m_src
;
4688 const program_point
&src_point
= src_enode
.get_point ();
4689 const gimple
*last_stmt
4690 = src_point
.get_supernode ()->get_last_stmt ();
4691 *out
= make_unique
<feasibility_problem
> (edge_idx
, *eedge
,
4701 logger
->log ("state after edge %i: EN:%i -> EN:%i",
4703 eedge
->m_src
->m_index
,
4704 eedge
->m_dest
->m_index
);
4705 logger
->start_log_line ();
4706 state
.get_model ().dump_to_pp (logger
->get_printer (), true, false);
4707 logger
->end_log_line ();
4714 /* Dump this path in multiline form to PP.
4715 If EXT_STATE is non-NULL, then show the nodes. */
4718 exploded_path::dump_to_pp (pretty_printer
*pp
,
4719 const extrinsic_state
*ext_state
) const
4721 for (unsigned i
= 0; i
< m_edges
.length (); i
++)
4723 const exploded_edge
*eedge
= m_edges
[i
];
4724 pp_printf (pp
, "m_edges[%i]: EN %i -> EN %i",
4726 eedge
->m_src
->m_index
,
4727 eedge
->m_dest
->m_index
);
4731 eedge
->m_dest
->dump_to_pp (pp
, *ext_state
);
4735 /* Dump this path in multiline form to FP. */
4738 exploded_path::dump (FILE *fp
, const extrinsic_state
*ext_state
) const
4741 pp_format_decoder (&pp
) = default_tree_printer
;
4742 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
4743 pp
.buffer
->stream
= fp
;
4744 dump_to_pp (&pp
, ext_state
);
4748 /* Dump this path in multiline form to stderr. */
4751 exploded_path::dump (const extrinsic_state
*ext_state
) const
4753 dump (stderr
, ext_state
);
4756 /* Dump this path verbosely to FILENAME. */
4759 exploded_path::dump_to_file (const char *filename
,
4760 const extrinsic_state
&ext_state
) const
4762 FILE *fp
= fopen (filename
, "w");
4766 pp_format_decoder (&pp
) = default_tree_printer
;
4767 pp
.buffer
->stream
= fp
;
4768 dump_to_pp (&pp
, &ext_state
);
4773 /* class feasibility_problem. */
4776 feasibility_problem::dump_to_pp (pretty_printer
*pp
) const
4778 pp_printf (pp
, "edge from EN: %i to EN: %i",
4779 m_eedge
.m_src
->m_index
, m_eedge
.m_dest
->m_index
);
4782 pp_string (pp
, "; rejected constraint: ");
4783 m_rc
->dump_to_pp (pp
);
4784 pp_string (pp
, "; rmodel: ");
4785 m_rc
->get_model ().dump_to_pp (pp
, true, false);
4789 /* class feasibility_state. */
4791 /* Ctor for feasibility_state, at the beginning of a path. */
4793 feasibility_state::feasibility_state (region_model_manager
*manager
,
4794 const supergraph
&sg
)
4795 : m_model (manager
),
4796 m_snodes_visited (sg
.m_nodes
.length ())
4798 bitmap_clear (m_snodes_visited
);
4801 /* Copy ctor for feasibility_state, for extending a path. */
4803 feasibility_state::feasibility_state (const feasibility_state
&other
)
4804 : m_model (other
.m_model
),
4805 m_snodes_visited (const_sbitmap (other
.m_snodes_visited
)->n_bits
)
4807 bitmap_copy (m_snodes_visited
, other
.m_snodes_visited
);
4810 /* The heart of feasibility-checking.
4812 Attempt to update this state in-place based on traversing EEDGE
4814 Update the model for the stmts in the src enode.
4815 Attempt to add constraints for EEDGE.
4817 If feasible, return true.
4818 Otherwise, return false and write to *OUT_RC. */
4821 feasibility_state::maybe_update_for_edge (logger
*logger
,
4822 const exploded_edge
*eedge
,
4823 rejected_constraint
**out_rc
)
4825 const exploded_node
&src_enode
= *eedge
->m_src
;
4826 const program_point
&src_point
= src_enode
.get_point ();
4829 logger
->start_log_line ();
4830 src_point
.print (logger
->get_printer (), format (false));
4831 logger
->end_log_line ();
4834 /* Update state for the stmts that were processed in each enode. */
4835 for (unsigned stmt_idx
= 0; stmt_idx
< src_enode
.m_num_processed_stmts
;
4838 const gimple
*stmt
= src_enode
.get_processed_stmt (stmt_idx
);
4840 /* Update cfun and input_location in case of ICE: make it easier to
4841 track down which source construct we're failing to handle. */
4842 auto_cfun
sentinel (src_point
.get_function ());
4843 input_location
= stmt
->location
;
4845 update_for_stmt (stmt
);
4848 const superedge
*sedge
= eedge
->m_sedge
;
4853 label_text
desc (sedge
->get_description (false));
4854 logger
->log (" sedge: SN:%i -> SN:%i %s",
4855 sedge
->m_src
->m_index
,
4856 sedge
->m_dest
->m_index
,
4860 const gimple
*last_stmt
= src_point
.get_supernode ()->get_last_stmt ();
4861 if (!m_model
.maybe_update_for_edge (*sedge
, last_stmt
, NULL
, out_rc
))
4865 logger
->log ("rejecting due to region model");
4866 m_model
.dump_to_pp (logger
->get_printer (), true, false);
4873 /* Special-case the initial eedge from the origin node to the
4874 initial function by pushing a frame for it. */
4875 if (src_point
.get_kind () == PK_ORIGIN
)
4877 gcc_assert (eedge
->m_src
->m_index
== 0);
4878 gcc_assert (eedge
->m_dest
->get_point ().get_kind ()
4879 == PK_BEFORE_SUPERNODE
);
4880 function
*fun
= eedge
->m_dest
->get_function ();
4882 m_model
.push_frame (fun
, NULL
, NULL
);
4884 logger
->log (" pushing frame for %qD", fun
->decl
);
4886 else if (eedge
->m_custom_info
)
4888 eedge
->m_custom_info
->update_model (&m_model
, eedge
, NULL
);
4892 /* Handle phi nodes on an edge leaving a PK_BEFORE_SUPERNODE (to
4893 a PK_BEFORE_STMT, or a PK_AFTER_SUPERNODE if no stmts).
4894 This will typically not be associated with a superedge. */
4895 if (src_point
.get_from_edge ())
4897 const cfg_superedge
*last_cfg_superedge
4898 = src_point
.get_from_edge ()->dyn_cast_cfg_superedge ();
4899 const exploded_node
&dst_enode
= *eedge
->m_dest
;
4900 const unsigned dst_snode_idx
= dst_enode
.get_supernode ()->m_index
;
4901 if (last_cfg_superedge
)
4904 logger
->log (" update for phis");
4905 m_model
.update_for_phis (src_enode
.get_supernode (),
4908 /* If we've entering an snode that we've already visited on this
4909 epath, then we need do fix things up for loops; see the
4910 comment for store::loop_replay_fixup.
4911 Perhaps we should probably also verify the callstring,
4912 and track program_points, but hopefully doing it by supernode
4914 if (bitmap_bit_p (m_snodes_visited
, dst_snode_idx
))
4915 m_model
.loop_replay_fixup (dst_enode
.get_state ().m_region_model
);
4917 bitmap_set_bit (m_snodes_visited
, dst_snode_idx
);
4922 /* Update this object for the effects of STMT. */
4925 feasibility_state::update_for_stmt (const gimple
*stmt
)
4927 if (const gassign
*assign
= dyn_cast
<const gassign
*> (stmt
))
4928 m_model
.on_assignment (assign
, NULL
);
4929 else if (const gasm
*asm_stmt
= dyn_cast
<const gasm
*> (stmt
))
4930 m_model
.on_asm_stmt (asm_stmt
, NULL
);
4931 else if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
4933 bool unknown_side_effects
= m_model
.on_call_pre (call
, NULL
);
4934 m_model
.on_call_post (call
, unknown_side_effects
, NULL
);
4936 else if (const greturn
*return_
= dyn_cast
<const greturn
*> (stmt
))
4937 m_model
.on_return (return_
, NULL
);
4940 /* Dump this object to PP. */
4943 feasibility_state::dump_to_pp (pretty_printer
*pp
,
4944 bool simple
, bool multiline
) const
4946 m_model
.dump_to_pp (pp
, simple
, multiline
);
4949 /* A family of cluster subclasses for use when generating .dot output for
4950 exploded graphs (-fdump-analyzer-exploded-graph), for grouping the
4951 enodes into hierarchical boxes.
4953 All functionless enodes appear in the top-level graph.
4954 Every (function, call_string) pair gets its own cluster. Within that
4955 cluster, each supernode gets its own cluster.
4957 Hence all enodes relating to a particular function with a particular
4958 callstring will be in a cluster together; all enodes for the same
4959 function but with a different callstring will be in a different
4962 /* Base class of cluster for clustering exploded_node instances in .dot
4963 output, based on various subclass-specific criteria. */
4965 class exploded_cluster
: public cluster
<eg_traits
>
4969 /* Cluster containing all exploded_node instances for one supernode. */
4971 class supernode_cluster
: public exploded_cluster
4974 supernode_cluster (const supernode
*supernode
) : m_supernode (supernode
) {}
4978 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const final override
4980 gv
->println ("subgraph \"cluster_supernode_%i\" {", m_supernode
->m_index
);
4982 gv
->println ("style=\"dashed\";");
4983 gv
->println ("label=\"SN: %i (bb: %i; scc: %i)\";",
4984 m_supernode
->m_index
, m_supernode
->m_bb
->index
,
4985 args
.m_eg
.get_scc_id (*m_supernode
));
4988 exploded_node
*enode
;
4989 FOR_EACH_VEC_ELT (m_enodes
, i
, enode
)
4990 enode
->dump_dot (gv
, args
);
4992 /* Terminate subgraph. */
4997 void add_node (exploded_node
*en
) final override
4999 m_enodes
.safe_push (en
);
5002 /* Comparator for use by auto_vec<supernode_cluster *>::qsort. */
5004 static int cmp_ptr_ptr (const void *p1
, const void *p2
)
5006 const supernode_cluster
*c1
5007 = *(const supernode_cluster
* const *)p1
;
5008 const supernode_cluster
*c2
5009 = *(const supernode_cluster
* const *)p2
;
5010 return c1
->m_supernode
->m_index
- c2
->m_supernode
->m_index
;
5014 const supernode
*m_supernode
;
5015 auto_vec
<exploded_node
*> m_enodes
;
5018 /* Cluster containing all supernode_cluster instances for one
5019 (function, call_string) pair. */
5021 class function_call_string_cluster
: public exploded_cluster
5024 function_call_string_cluster (function
*fun
, const call_string
&cs
)
5025 : m_fun (fun
), m_cs (cs
) {}
5027 ~function_call_string_cluster ()
5029 for (map_t::iterator iter
= m_map
.begin ();
5030 iter
!= m_map
.end ();
5032 delete (*iter
).second
;
5035 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const final override
5037 const char *funcname
= function_name (m_fun
);
5039 gv
->println ("subgraph \"cluster_function_%s\" {",
5040 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (m_fun
->decl
)));
5042 gv
->write_indent ();
5043 gv
->print ("label=\"call string: ");
5044 m_cs
.print (gv
->get_pp ());
5045 gv
->print (" function: %s \";", funcname
);
5048 /* Dump m_map, sorting it to avoid churn when comparing dumps. */
5049 auto_vec
<supernode_cluster
*> child_clusters (m_map
.elements ());
5050 for (map_t::iterator iter
= m_map
.begin ();
5051 iter
!= m_map
.end ();
5053 child_clusters
.quick_push ((*iter
).second
);
5055 child_clusters
.qsort (supernode_cluster::cmp_ptr_ptr
);
5058 supernode_cluster
*child_cluster
;
5059 FOR_EACH_VEC_ELT (child_clusters
, i
, child_cluster
)
5060 child_cluster
->dump_dot (gv
, args
);
5062 /* Terminate subgraph. */
5067 void add_node (exploded_node
*en
) final override
5069 const supernode
*supernode
= en
->get_supernode ();
5070 gcc_assert (supernode
);
5071 supernode_cluster
**slot
= m_map
.get (supernode
);
5073 (*slot
)->add_node (en
);
5076 supernode_cluster
*child
= new supernode_cluster (supernode
);
5077 m_map
.put (supernode
, child
);
5078 child
->add_node (en
);
5082 /* Comparator for use by auto_vec<function_call_string_cluster *>. */
5084 static int cmp_ptr_ptr (const void *p1
, const void *p2
)
5086 const function_call_string_cluster
*c1
5087 = *(const function_call_string_cluster
* const *)p1
;
5088 const function_call_string_cluster
*c2
5089 = *(const function_call_string_cluster
* const *)p2
;
5091 = strcmp (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c1
->m_fun
->decl
)),
5092 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c2
->m_fun
->decl
))))
5094 return call_string::cmp (c1
->m_cs
, c2
->m_cs
);
5099 const call_string
&m_cs
;
5100 typedef ordered_hash_map
<const supernode
*, supernode_cluster
*> map_t
;
5104 /* Keys for root_cluster. */
5106 struct function_call_string
5108 function_call_string (function
*fun
, const call_string
*cs
)
5109 : m_fun (fun
), m_cs (cs
)
5116 const call_string
*m_cs
;
5121 template <> struct default_hash_traits
<function_call_string
>
5122 : public pod_hash_traits
<function_call_string
>
5124 static const bool empty_zero_p
= false;
5129 pod_hash_traits
<function_call_string
>::hash (value_type v
)
5131 return (pointer_hash
<function
>::hash (v
.m_fun
)
5132 ^ pointer_hash
<const call_string
>::hash (v
.m_cs
));
5137 pod_hash_traits
<function_call_string
>::equal (const value_type
&existing
,
5138 const value_type
&candidate
)
5140 return existing
.m_fun
== candidate
.m_fun
&& &existing
.m_cs
== &candidate
.m_cs
;
5144 pod_hash_traits
<function_call_string
>::mark_deleted (value_type
&v
)
5146 v
.m_fun
= reinterpret_cast<function
*> (1);
5150 pod_hash_traits
<function_call_string
>::mark_empty (value_type
&v
)
5156 pod_hash_traits
<function_call_string
>::is_deleted (value_type v
)
5158 return v
.m_fun
== reinterpret_cast<function
*> (1);
5162 pod_hash_traits
<function_call_string
>::is_empty (value_type v
)
5164 return v
.m_fun
== NULL
;
5169 /* Top-level cluster for generating .dot output for exploded graphs,
5170 handling the functionless nodes, and grouping the remaining nodes by
5173 class root_cluster
: public exploded_cluster
5178 for (map_t::iterator iter
= m_map
.begin ();
5179 iter
!= m_map
.end ();
5181 delete (*iter
).second
;
5184 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const final override
5187 exploded_node
*enode
;
5188 FOR_EACH_VEC_ELT (m_functionless_enodes
, i
, enode
)
5189 enode
->dump_dot (gv
, args
);
5191 /* Dump m_map, sorting it to avoid churn when comparing dumps. */
5192 auto_vec
<function_call_string_cluster
*> child_clusters (m_map
.elements ());
5193 for (map_t::iterator iter
= m_map
.begin ();
5194 iter
!= m_map
.end ();
5196 child_clusters
.quick_push ((*iter
).second
);
5198 child_clusters
.qsort (function_call_string_cluster::cmp_ptr_ptr
);
5200 function_call_string_cluster
*child_cluster
;
5201 FOR_EACH_VEC_ELT (child_clusters
, i
, child_cluster
)
5202 child_cluster
->dump_dot (gv
, args
);
5205 void add_node (exploded_node
*en
) final override
5207 function
*fun
= en
->get_function ();
5210 m_functionless_enodes
.safe_push (en
);
5214 const call_string
&cs
= en
->get_point ().get_call_string ();
5215 function_call_string
key (fun
, &cs
);
5216 function_call_string_cluster
**slot
= m_map
.get (key
);
5218 (*slot
)->add_node (en
);
5221 function_call_string_cluster
*child
5222 = new function_call_string_cluster (fun
, cs
);
5223 m_map
.put (key
, child
);
5224 child
->add_node (en
);
5229 typedef hash_map
<function_call_string
, function_call_string_cluster
*> map_t
;
5232 /* This should just be the origin exploded_node. */
5233 auto_vec
<exploded_node
*> m_functionless_enodes
;
5236 /* Subclass of range_label for use within
5237 exploded_graph::dump_exploded_nodes for implementing
5238 -fdump-analyzer-exploded-nodes: a label for a specific
5241 class enode_label
: public range_label
5244 enode_label (const extrinsic_state
&ext_state
,
5245 exploded_node
*enode
)
5246 : m_ext_state (ext_state
), m_enode (enode
) {}
5248 label_text
get_text (unsigned) const final override
5251 pp_format_decoder (&pp
) = default_tree_printer
;
5252 m_enode
->get_state ().dump_to_pp (m_ext_state
, true, false, &pp
);
5253 return make_label_text (false, "EN: %i: %s",
5254 m_enode
->m_index
, pp_formatted_text (&pp
));
5258 const extrinsic_state
&m_ext_state
;
5259 exploded_node
*m_enode
;
5262 /* Postprocessing support for dumping the exploded nodes.
5263 Handle -fdump-analyzer-exploded-nodes,
5264 -fdump-analyzer-exploded-nodes-2, and the
5265 "__analyzer_dump_exploded_nodes" builtin. */
5268 exploded_graph::dump_exploded_nodes () const
5271 /* Locate calls to __analyzer_dump_exploded_nodes. */
5272 // Print how many egs there are for them?
5273 /* Better: log them as we go, and record the exploded nodes
5276 /* Show every enode. */
5278 /* Gather them by stmt, so that we can more clearly see the
5279 "hotspots" requiring numerous exploded nodes. */
5281 /* Alternatively, simply throw them all into one big rich_location
5282 and see if the label-printing will sort it out...
5283 This requires them all to be in the same source file. */
5285 if (flag_dump_analyzer_exploded_nodes
)
5287 auto_timevar
tv (TV_ANALYZER_DUMP
);
5288 gcc_rich_location
richloc (UNKNOWN_LOCATION
);
5290 exploded_node
*enode
;
5291 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
5293 if (const gimple
*stmt
= enode
->get_stmt ())
5295 if (get_pure_location (richloc
.get_loc ()) == UNKNOWN_LOCATION
)
5296 richloc
.set_range (0, stmt
->location
, SHOW_RANGE_WITH_CARET
);
5298 richloc
.add_range (stmt
->location
,
5299 SHOW_RANGE_WITHOUT_CARET
,
5300 new enode_label (m_ext_state
, enode
));
5303 warning_at (&richloc
, 0, "%i exploded nodes", m_nodes
.length ());
5305 /* Repeat the warning without all the labels, so that message is visible
5306 (the other one may well have scrolled past the terminal limit). */
5307 warning_at (richloc
.get_loc (), 0,
5308 "%i exploded nodes", m_nodes
.length ());
5310 if (m_worklist
.length () > 0)
5311 warning_at (richloc
.get_loc (), 0,
5312 "worklist still contains %i nodes", m_worklist
.length ());
5315 /* Dump the egraph in textual form to a dump file. */
5316 if (flag_dump_analyzer_exploded_nodes_2
)
5318 auto_timevar
tv (TV_ANALYZER_DUMP
);
5320 = concat (dump_base_name
, ".eg.txt", NULL
);
5321 FILE *outf
= fopen (filename
, "w");
5323 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
5326 fprintf (outf
, "exploded graph for %s\n", dump_base_name
);
5327 fprintf (outf
, " nodes: %i\n", m_nodes
.length ());
5328 fprintf (outf
, " edges: %i\n", m_edges
.length ());
5331 exploded_node
*enode
;
5332 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
5334 fprintf (outf
, "\nEN %i:\n", enode
->m_index
);
5335 enode
->dump_succs_and_preds (outf
);
5337 enode
->get_point ().print (&pp
, format (true));
5338 fprintf (outf
, "%s\n", pp_formatted_text (&pp
));
5339 enode
->get_state ().dump_to_file (m_ext_state
, false, true, outf
);
5345 /* Dump the egraph in textual form to multiple dump files, one per enode. */
5346 if (flag_dump_analyzer_exploded_nodes_3
)
5348 auto_timevar
tv (TV_ANALYZER_DUMP
);
5351 exploded_node
*enode
;
5352 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
5355 = xasprintf ("%s.en-%i.txt", dump_base_name
, i
);
5356 FILE *outf
= fopen (filename
, "w");
5358 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
5361 fprintf (outf
, "EN %i:\n", enode
->m_index
);
5362 enode
->dump_succs_and_preds (outf
);
5364 enode
->get_point ().print (&pp
, format (true));
5365 fprintf (outf
, "%s\n", pp_formatted_text (&pp
));
5366 enode
->get_state ().dump_to_file (m_ext_state
, false, true, outf
);
5372 /* Emit a warning at any call to "__analyzer_dump_exploded_nodes",
5373 giving the number of processed exploded nodes for "before-stmt",
5374 and the IDs of processed, merger, and worklist enodes.
5376 We highlight the count of *processed* enodes since this is of most
5377 interest in DejaGnu tests for ensuring that state merger has
5380 We don't show the count of merger and worklist enodes, as this is
5381 more of an implementation detail of the merging/worklist that we
5382 don't want to bake into our expected DejaGnu messages. */
5385 exploded_node
*enode
;
5386 hash_set
<const gimple
*> seen
;
5387 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
5389 if (enode
->get_point ().get_kind () != PK_BEFORE_STMT
)
5392 if (const gimple
*stmt
= enode
->get_stmt ())
5393 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
5394 if (is_special_named_call_p (call
, "__analyzer_dump_exploded_nodes",
5397 if (seen
.contains (stmt
))
5400 auto_vec
<exploded_node
*> processed_enodes
;
5401 auto_vec
<exploded_node
*> merger_enodes
;
5402 auto_vec
<exploded_node
*> worklist_enodes
;
5403 /* This is O(N^2). */
5405 exploded_node
*other_enode
;
5406 FOR_EACH_VEC_ELT (m_nodes
, j
, other_enode
)
5408 if (other_enode
->get_point ().get_kind () != PK_BEFORE_STMT
)
5410 if (other_enode
->get_stmt () == stmt
)
5411 switch (other_enode
->get_status ())
5415 case exploded_node::STATUS_WORKLIST
:
5416 worklist_enodes
.safe_push (other_enode
);
5418 case exploded_node::STATUS_PROCESSED
:
5419 processed_enodes
.safe_push (other_enode
);
5421 case exploded_node::STATUS_MERGER
:
5422 merger_enodes
.safe_push (other_enode
);
5428 pp_character (&pp
, '[');
5429 print_enode_indices (&pp
, processed_enodes
);
5430 if (merger_enodes
.length () > 0)
5432 pp_string (&pp
, "] merger(s): [");
5433 print_enode_indices (&pp
, merger_enodes
);
5435 if (worklist_enodes
.length () > 0)
5437 pp_string (&pp
, "] worklist: [");
5438 print_enode_indices (&pp
, worklist_enodes
);
5440 pp_character (&pp
, ']');
5442 warning_n (stmt
->location
, 0, processed_enodes
.length (),
5443 "%i processed enode: %s",
5444 "%i processed enodes: %s",
5445 processed_enodes
.length (), pp_formatted_text (&pp
));
5448 /* If the argument is non-zero, then print all of the states
5449 of the various enodes. */
5450 tree t_arg
= fold (gimple_call_arg (call
, 0));
5451 if (TREE_CODE (t_arg
) != INTEGER_CST
)
5453 error_at (call
->location
,
5454 "integer constant required for arg 1");
5457 int i_arg
= TREE_INT_CST_LOW (t_arg
);
5460 exploded_node
*other_enode
;
5461 FOR_EACH_VEC_ELT (processed_enodes
, j
, other_enode
)
5463 fprintf (stderr
, "%i of %i: EN %i:\n",
5464 j
+ 1, processed_enodes
.length (),
5465 other_enode
->m_index
);
5466 other_enode
->dump_succs_and_preds (stderr
);
5468 other_enode
->get_state ().dump (m_ext_state
, false);
5475 DEBUG_FUNCTION exploded_node
*
5476 exploded_graph::get_node_by_index (int idx
) const
5478 exploded_node
*enode
= m_nodes
[idx
];
5479 gcc_assert (enode
->m_index
== idx
);
5483 /* Ensure that there is an exploded_node for a top-level call to FNDECL. */
5486 exploded_graph::on_escaped_function (tree fndecl
)
5488 logger
* const logger
= get_logger ();
5489 LOG_FUNC_1 (logger
, "%qE", fndecl
);
5491 cgraph_node
*cgnode
= cgraph_node::get (fndecl
);
5495 function
*fun
= cgnode
->get_fun ();
5499 if (!gimple_has_body_p (fndecl
))
5502 exploded_node
*enode
= add_function_entry (fun
);
5506 logger
->log ("created EN %i for %qE entrypoint",
5507 enode
->m_index
, fun
->decl
);
5509 logger
->log ("did not create enode for %qE entrypoint", fun
->decl
);
5513 /* A collection of classes for visualizing the callgraph in .dot form
5514 (as represented in the supergraph). */
5516 /* Forward decls. */
5517 class viz_callgraph_node
;
5518 class viz_callgraph_edge
;
5519 class viz_callgraph
;
5520 class viz_callgraph_cluster
;
5522 /* Traits for using "digraph.h" to visualize the callgraph. */
5524 struct viz_callgraph_traits
5526 typedef viz_callgraph_node node_t
;
5527 typedef viz_callgraph_edge edge_t
;
5528 typedef viz_callgraph graph_t
;
5531 dump_args_t (const exploded_graph
*eg
) : m_eg (eg
) {}
5532 const exploded_graph
*m_eg
;
5534 typedef viz_callgraph_cluster cluster_t
;
5537 /* Subclass of dnode representing a function within the callgraph. */
5539 class viz_callgraph_node
: public dnode
<viz_callgraph_traits
>
5541 friend class viz_callgraph
;
5544 viz_callgraph_node (function
*fun
, int index
)
5545 : m_fun (fun
), m_index (index
), m_num_supernodes (0), m_num_superedges (0)
5550 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const final override
5552 pretty_printer
*pp
= gv
->get_pp ();
5555 pp_printf (pp
, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
5557 pp_write_text_to_stream (pp
);
5559 pp_printf (pp
, "VCG: %i: %s", m_index
, function_name (m_fun
));
5562 pp_printf (pp
, "supernodes: %i\n", m_num_supernodes
);
5565 pp_printf (pp
, "superedges: %i\n", m_num_superedges
);
5571 exploded_node
*enode
;
5572 unsigned num_enodes
= 0;
5573 FOR_EACH_VEC_ELT (args
.m_eg
->m_nodes
, i
, enode
)
5575 if (enode
->get_point ().get_function () == m_fun
)
5578 pp_printf (pp
, "enodes: %i\n", num_enodes
);
5581 // TODO: also show the per-callstring breakdown
5582 const exploded_graph::call_string_data_map_t
*per_cs_data
5583 = args
.m_eg
->get_per_call_string_data ();
5584 for (exploded_graph::call_string_data_map_t::iterator iter
5585 = per_cs_data
->begin ();
5586 iter
!= per_cs_data
->end ();
5589 const call_string
*cs
= (*iter
).first
;
5590 //per_call_string_data *data = (*iter).second;
5592 FOR_EACH_VEC_ELT (args
.m_eg
->m_nodes
, i
, enode
)
5594 if (enode
->get_point ().get_function () == m_fun
5595 && &enode
->get_point ().get_call_string () == cs
)
5601 pp_printf (pp
, ": %i\n", num_enodes
);
5605 /* Show any summaries. */
5606 per_function_data
*data
= args
.m_eg
->get_per_function_data (m_fun
);
5610 pp_printf (pp
, "summaries: %i\n", data
->m_summaries
.length ());
5611 for (auto summary
: data
->m_summaries
)
5613 pp_printf (pp
, "\nsummary: %s:\n", summary
->get_desc ().get ());
5614 const extrinsic_state
&ext_state
= args
.m_eg
->get_ext_state ();
5615 const program_state
&state
= summary
->get_state ();
5616 state
.dump_to_pp (ext_state
, false, true, pp
);
5622 pp_write_text_as_dot_label_to_stream (pp
, /*for_record=*/true);
5623 pp_string (pp
, "\"];\n\n");
5627 void dump_dot_id (pretty_printer
*pp
) const
5629 pp_printf (pp
, "vcg_%i", m_index
);
5635 int m_num_supernodes
;
5636 int m_num_superedges
;
5639 /* Subclass of dedge representing a callgraph edge. */
5641 class viz_callgraph_edge
: public dedge
<viz_callgraph_traits
>
5644 viz_callgraph_edge (viz_callgraph_node
*src
, viz_callgraph_node
*dest
)
5645 : dedge
<viz_callgraph_traits
> (src
, dest
)
5648 void dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
5651 pretty_printer
*pp
= gv
->get_pp ();
5653 const char *style
= "\"solid,bold\"";
5654 const char *color
= "black";
5656 const char *constraint
= "true";
5658 m_src
->dump_dot_id (pp
);
5659 pp_string (pp
, " -> ");
5660 m_dest
->dump_dot_id (pp
);
5662 (" [style=%s, color=%s, weight=%d, constraint=%s,"
5664 style
, color
, weight
, constraint
);
5665 pp_printf (pp
, "\"];\n");
5669 /* Subclass of digraph representing the callgraph. */
5671 class viz_callgraph
: public digraph
<viz_callgraph_traits
>
5674 viz_callgraph (const supergraph
&sg
);
5676 viz_callgraph_node
*get_vcg_node_for_function (function
*fun
)
5678 return *m_map
.get (fun
);
5681 viz_callgraph_node
*get_vcg_node_for_snode (supernode
*snode
)
5683 return get_vcg_node_for_function (snode
->m_fun
);
5687 hash_map
<function
*, viz_callgraph_node
*> m_map
;
5690 /* Placeholder subclass of cluster. */
5692 class viz_callgraph_cluster
: public cluster
<viz_callgraph_traits
>
5696 /* viz_callgraph's ctor. */
5698 viz_callgraph::viz_callgraph (const supergraph
&sg
)
5701 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5703 function
*fun
= node
->get_fun ();
5704 viz_callgraph_node
*vcg_node
5705 = new viz_callgraph_node (fun
, m_nodes
.length ());
5706 m_map
.put (fun
, vcg_node
);
5707 add_node (vcg_node
);
5712 FOR_EACH_VEC_ELT (sg
.m_edges
, i
, sedge
)
5714 viz_callgraph_node
*vcg_src
= get_vcg_node_for_snode (sedge
->m_src
);
5716 get_vcg_node_for_function (vcg_src
->m_fun
)->m_num_superedges
++;
5717 if (sedge
->dyn_cast_call_superedge ())
5719 viz_callgraph_node
*vcg_dest
= get_vcg_node_for_snode (sedge
->m_dest
);
5720 viz_callgraph_edge
*vcg_edge
5721 = new viz_callgraph_edge (vcg_src
, vcg_dest
);
5722 add_edge (vcg_edge
);
5727 FOR_EACH_VEC_ELT (sg
.m_nodes
, i
, snode
)
5730 get_vcg_node_for_function (snode
->m_fun
)->m_num_supernodes
++;
5734 /* Dump the callgraph to FILENAME. */
5737 dump_callgraph (const supergraph
&sg
, const char *filename
,
5738 const exploded_graph
*eg
)
5740 FILE *outf
= fopen (filename
, "w");
5745 viz_callgraph
vcg (sg
);
5746 vcg
.dump_dot (filename
, NULL
, viz_callgraph_traits::dump_args_t (eg
));
5751 /* Dump the callgraph to "<srcfile>.callgraph.dot". */
5754 dump_callgraph (const supergraph
&sg
, const exploded_graph
*eg
)
5756 auto_timevar
tv (TV_ANALYZER_DUMP
);
5757 char *filename
= concat (dump_base_name
, ".callgraph.dot", NULL
);
5758 dump_callgraph (sg
, filename
, eg
);
5762 /* Subclass of dot_annotator for implementing
5763 DUMP_BASE_NAME.supergraph-eg.dot, a post-analysis dump of the supergraph.
5765 Annotate the supergraph nodes by printing the exploded nodes in concise
5766 form within them, next to their pertinent statements where appropriate,
5767 colorizing the exploded nodes based on sm-state.
5768 Also show saved diagnostics within the exploded nodes, giving information
5769 on whether they were feasible, and, if infeasible, where the problem
5772 class exploded_graph_annotator
: public dot_annotator
5775 exploded_graph_annotator (const exploded_graph
&eg
)
5778 /* Avoid O(N^2) by prepopulating m_enodes_per_snodes. */
5781 FOR_EACH_VEC_ELT (eg
.get_supergraph ().m_nodes
, i
, snode
)
5782 m_enodes_per_snodes
.safe_push (new auto_vec
<exploded_node
*> ());
5783 exploded_node
*enode
;
5784 FOR_EACH_VEC_ELT (m_eg
.m_nodes
, i
, enode
)
5785 if (enode
->get_supernode ())
5786 m_enodes_per_snodes
[enode
->get_supernode ()->m_index
]->safe_push (enode
);
5789 /* Show exploded nodes for BEFORE_SUPERNODE points before N. */
5790 bool add_node_annotations (graphviz_out
*gv
, const supernode
&n
,
5792 const final override
5797 pretty_printer
*pp
= gv
->get_pp ();
5800 pp_string (pp
, "BEFORE");
5801 pp_printf (pp
, " (scc: %i)", m_eg
.get_scc_id (n
));
5805 exploded_node
*enode
;
5806 bool had_enode
= false;
5807 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[n
.m_index
], i
, enode
)
5809 gcc_assert (enode
->get_supernode () == &n
);
5810 const program_point
&point
= enode
->get_point ();
5811 if (point
.get_kind () != PK_BEFORE_SUPERNODE
)
5813 print_enode (gv
, enode
);
5817 pp_string (pp
, "<TD BGCOLOR=\"red\">UNREACHED</TD>");
5823 /* Show exploded nodes for STMT. */
5824 void add_stmt_annotations (graphviz_out
*gv
, const gimple
*stmt
,
5826 const final override
5830 pretty_printer
*pp
= gv
->get_pp ();
5832 const supernode
*snode
5833 = m_eg
.get_supergraph ().get_supernode_for_stmt (stmt
);
5835 exploded_node
*enode
;
5836 bool had_td
= false;
5837 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[snode
->m_index
], i
, enode
)
5839 const program_point
&point
= enode
->get_point ();
5840 if (point
.get_kind () != PK_BEFORE_STMT
)
5842 if (point
.get_stmt () != stmt
)
5844 print_enode (gv
, enode
);
5855 /* Show exploded nodes for AFTER_SUPERNODE points after N. */
5856 bool add_after_node_annotations (graphviz_out
*gv
, const supernode
&n
)
5857 const final override
5860 pretty_printer
*pp
= gv
->get_pp ();
5863 pp_string (pp
, "AFTER");
5867 exploded_node
*enode
;
5868 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[n
.m_index
], i
, enode
)
5870 gcc_assert (enode
->get_supernode () == &n
);
5871 const program_point
&point
= enode
->get_point ();
5872 if (point
.get_kind () != PK_AFTER_SUPERNODE
)
5874 print_enode (gv
, enode
);
5882 /* Concisely print a TD element for ENODE, showing the index, status,
5883 and any saved_diagnostics at the enode. Colorize it to show sm-state.
5885 Ideally we'd dump ENODE's state here, hidden behind some kind of
5886 interactive disclosure method like a tooltip, so that the states
5887 can be explored without overwhelming the graph.
5888 However, I wasn't able to get graphviz/xdot to show tooltips on
5889 individual elements within a HTML-like label. */
5890 void print_enode (graphviz_out
*gv
, const exploded_node
*enode
) const
5892 pretty_printer
*pp
= gv
->get_pp ();
5893 pp_printf (pp
, "<TD BGCOLOR=\"%s\">",
5894 enode
->get_dot_fillcolor ());
5895 pp_printf (pp
, "<TABLE BORDER=\"0\">");
5897 pp_printf (pp
, "EN: %i", enode
->m_index
);
5898 switch (enode
->get_status ())
5902 case exploded_node::STATUS_WORKLIST
:
5903 pp_string (pp
, "(W)");
5905 case exploded_node::STATUS_PROCESSED
:
5907 case exploded_node::STATUS_MERGER
:
5908 pp_string (pp
, "(M)");
5910 case exploded_node::STATUS_BULK_MERGED
:
5911 pp_string (pp
, "(BM)");
5916 /* Dump any saved_diagnostics at this enode. */
5917 for (unsigned i
= 0; i
< enode
->get_num_diagnostics (); i
++)
5919 const saved_diagnostic
*sd
= enode
->get_saved_diagnostic (i
);
5920 print_saved_diagnostic (gv
, sd
);
5922 pp_printf (pp
, "</TABLE>");
5923 pp_printf (pp
, "</TD>");
5926 /* Print a TABLE element for SD, showing the kind, the length of the
5927 exploded_path, whether the path was feasible, and if infeasible,
5928 what the problem was. */
5929 void print_saved_diagnostic (graphviz_out
*gv
,
5930 const saved_diagnostic
*sd
) const
5932 pretty_printer
*pp
= gv
->get_pp ();
5934 pp_printf (pp
, "<TABLE BORDER=\"0\">");
5936 pp_string (pp
, "<TD BGCOLOR=\"green\">");
5937 pp_printf (pp
, "DIAGNOSTIC: %s", sd
->m_d
->get_kind ());
5940 if (sd
->get_best_epath ())
5941 pp_printf (pp
, "epath length: %i", sd
->get_epath_length ());
5943 pp_printf (pp
, "no best epath");
5945 if (const feasibility_problem
*p
= sd
->get_feasibility_problem ())
5948 pp_printf (pp
, "INFEASIBLE at eedge %i: EN:%i -> EN:%i",
5950 p
->m_eedge
.m_src
->m_index
,
5951 p
->m_eedge
.m_dest
->m_index
);
5952 pp_write_text_as_html_like_dot_to_stream (pp
);
5955 p
->m_eedge
.m_sedge
->dump (pp
);
5956 pp_write_text_as_html_like_dot_to_stream (pp
);
5959 pp_gimple_stmt_1 (pp
, p
->m_last_stmt
, 0, (dump_flags_t
)0);
5960 pp_write_text_as_html_like_dot_to_stream (pp
);
5962 /* Ideally we'd print p->m_model here; see the notes above about
5965 pp_printf (pp
, "</TABLE>");
5969 const exploded_graph
&m_eg
;
5970 auto_delete_vec
<auto_vec
<exploded_node
*> > m_enodes_per_snodes
;
5973 /* Implement -fdump-analyzer-json. */
5976 dump_analyzer_json (const supergraph
&sg
,
5977 const exploded_graph
&eg
)
5979 auto_timevar
tv (TV_ANALYZER_DUMP
);
5980 char *filename
= concat (dump_base_name
, ".analyzer.json.gz", NULL
);
5981 gzFile output
= gzopen (filename
, "w");
5984 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
5989 json::object
*toplev_obj
= new json::object ();
5990 toplev_obj
->set ("sgraph", sg
.to_json ());
5991 toplev_obj
->set ("egraph", eg
.to_json ());
5994 toplev_obj
->print (&pp
);
5995 pp_formatted_text (&pp
);
5999 if (gzputs (output
, pp_formatted_text (&pp
)) == EOF
6000 || gzclose (output
))
6001 error_at (UNKNOWN_LOCATION
, "error writing %qs", filename
);
6006 /* Concrete subclass of plugin_analyzer_init_iface, allowing plugins
6007 to register new state machines. */
6009 class plugin_analyzer_init_impl
: public plugin_analyzer_init_iface
6012 plugin_analyzer_init_impl (auto_delete_vec
<state_machine
> *checkers
,
6013 known_function_manager
*known_fn_mgr
,
6015 : m_checkers (checkers
),
6016 m_known_fn_mgr (known_fn_mgr
),
6020 void register_state_machine (std::unique_ptr
<state_machine
> sm
) final override
6022 LOG_SCOPE (m_logger
);
6023 m_checkers
->safe_push (sm
.release ());
6026 void register_known_function (const char *name
,
6027 std::unique_ptr
<known_function
> kf
) final override
6029 LOG_SCOPE (m_logger
);
6030 m_known_fn_mgr
->add (name
, std::move (kf
));
6033 logger
*get_logger () const final override
6039 auto_delete_vec
<state_machine
> *m_checkers
;
6040 known_function_manager
*m_known_fn_mgr
;
6044 /* Run the analysis "engine". */
6047 impl_run_checkers (logger
*logger
)
6053 logger
->log ("BITS_BIG_ENDIAN: %i", BITS_BIG_ENDIAN
? 1 : 0);
6054 logger
->log ("BYTES_BIG_ENDIAN: %i", BYTES_BIG_ENDIAN
? 1 : 0);
6055 logger
->log ("WORDS_BIG_ENDIAN: %i", WORDS_BIG_ENDIAN
? 1 : 0);
6056 log_stashed_constants (logger
);
6059 /* If using LTO, ensure that the cgraph nodes have function bodies. */
6061 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
6062 node
->get_untransformed_body ();
6064 /* Create the supergraph. */
6065 supergraph
sg (logger
);
6067 engine
eng (&sg
, logger
);
6069 state_purge_map
*purge_map
= NULL
;
6071 if (flag_analyzer_state_purge
)
6072 purge_map
= new state_purge_map (sg
, eng
.get_model_manager (), logger
);
6074 if (flag_dump_analyzer_supergraph
)
6076 /* Dump supergraph pre-analysis. */
6077 auto_timevar
tv (TV_ANALYZER_DUMP
);
6078 char *filename
= concat (dump_base_name
, ".supergraph.dot", NULL
);
6079 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, NULL
);
6080 sg
.dump_dot (filename
, args
);
6084 if (flag_dump_analyzer_state_purge
)
6086 auto_timevar
tv (TV_ANALYZER_DUMP
);
6087 state_purge_annotator
a (purge_map
);
6088 char *filename
= concat (dump_base_name
, ".state-purge.dot", NULL
);
6089 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, &a
);
6090 sg
.dump_dot (filename
, args
);
6094 auto_delete_vec
<state_machine
> checkers
;
6095 make_checkers (checkers
, logger
);
6097 register_known_functions (*eng
.get_known_function_manager ());
6099 plugin_analyzer_init_impl
data (&checkers
,
6100 eng
.get_known_function_manager (),
6102 invoke_plugin_callbacks (PLUGIN_ANALYZER_INIT
, &data
);
6108 FOR_EACH_VEC_ELT (checkers
, i
, sm
)
6109 logger
->log ("checkers[%i]: %s", i
, sm
->get_name ());
6112 /* Extrinsic state shared by nodes in the graph. */
6113 const extrinsic_state
ext_state (checkers
, &eng
, logger
);
6115 const analysis_plan
plan (sg
, logger
);
6117 /* The exploded graph. */
6118 exploded_graph
eg (sg
, logger
, ext_state
, purge_map
, plan
,
6119 analyzer_verbosity
);
6121 /* Add entrypoints to the graph for externally-callable functions. */
6122 eg
.build_initial_worklist ();
6124 /* Now process the worklist, exploring the <point, state> graph. */
6125 eg
.process_worklist ();
6127 if (flag_dump_analyzer_exploded_graph
)
6129 auto_timevar
tv (TV_ANALYZER_DUMP
);
6131 = concat (dump_base_name
, ".eg.dot", NULL
);
6132 exploded_graph::dump_args_t
args (eg
);
6134 eg
.dump_dot (filename
, &c
, args
);
6138 /* Now emit any saved diagnostics. */
6139 eg
.get_diagnostic_manager ().emit_saved_diagnostics (eg
);
6141 eg
.dump_exploded_nodes ();
6145 if (flag_dump_analyzer_callgraph
)
6146 dump_callgraph (sg
, &eg
);
6148 if (flag_dump_analyzer_supergraph
)
6150 /* Dump post-analysis form of supergraph. */
6151 auto_timevar
tv (TV_ANALYZER_DUMP
);
6152 char *filename
= concat (dump_base_name
, ".supergraph-eg.dot", NULL
);
6153 exploded_graph_annotator
a (eg
);
6154 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, &a
);
6155 sg
.dump_dot (filename
, args
);
6159 if (flag_dump_analyzer_json
)
6160 dump_analyzer_json (sg
, eg
);
6162 if (flag_dump_analyzer_untracked
)
6163 eng
.get_model_manager ()->dump_untracked_regions ();
6168 /* Handle -fdump-analyzer and -fdump-analyzer-stderr. */
6169 static FILE *dump_fout
= NULL
;
6171 /* Track if we're responsible for closing dump_fout. */
6172 static bool owns_dump_fout
= false;
6174 /* If dumping is enabled, attempt to create dump_fout if it hasn't already
6175 been opened. Return it. */
6178 get_or_create_any_logfile ()
6182 if (flag_dump_analyzer_stderr
)
6184 else if (flag_dump_analyzer
)
6186 char *dump_filename
= concat (dump_base_name
, ".analyzer.txt", NULL
);
6187 dump_fout
= fopen (dump_filename
, "w");
6188 free (dump_filename
);
6190 owns_dump_fout
= true;
6196 /* External entrypoint to the analysis "engine".
6197 Set up any dumps, then call impl_run_checkers. */
6202 /* Save input_location. */
6203 location_t saved_input_location
= input_location
;
6206 log_user
the_logger (NULL
);
6207 get_or_create_any_logfile ();
6209 the_logger
.set_logger (new logger (dump_fout
, 0, 0,
6210 *global_dc
->printer
));
6211 LOG_SCOPE (the_logger
.get_logger ());
6213 impl_run_checkers (the_logger
.get_logger ());
6215 /* end of lifetime of the_logger (so that dump file is closed after the
6216 various dtors run). */
6222 owns_dump_fout
= false;
6226 /* Restore input_location. Subsequent passes may assume that input_location
6227 is some arbitrary value *not* in the block tree, which might be violated
6228 if we didn't restore it. */
6229 input_location
= saved_input_location
;
6234 #endif /* #if ENABLE_ANALYZER */