1 /* Classes for representing the state of interest at a given path of analysis.
2 Copyright (C) 2019-2024 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
23 #define INCLUDE_VECTOR
25 #include "coretypes.h"
27 #include "diagnostic-core.h"
28 #include "diagnostic.h"
29 #include "analyzer/analyzer.h"
30 #include "analyzer/analyzer-logging.h"
31 #include "analyzer/sm.h"
34 #include "ordered-hash-map.h"
36 #include "analyzer/call-string.h"
37 #include "analyzer/program-point.h"
38 #include "analyzer/store.h"
39 #include "analyzer/region-model.h"
40 #include "analyzer/program-state.h"
41 #include "analyzer/constraint-manager.h"
42 #include "diagnostic-event-id.h"
43 #include "analyzer/pending-diagnostic.h"
44 #include "analyzer/diagnostic-manager.h"
46 #include "basic-block.h"
48 #include "gimple-iterator.h"
51 #include "analyzer/supergraph.h"
52 #include "analyzer/program-state.h"
53 #include "analyzer/exploded-graph.h"
54 #include "analyzer/state-purge.h"
55 #include "analyzer/call-summary.h"
56 #include "analyzer/analyzer-selftests.h"
57 #include "text-art/tree-widget.h"
58 #include "text-art/dump.h"
64 /* class extrinsic_state. */
66 /* Dump a multiline representation of this state to PP. */
69 extrinsic_state::dump_to_pp (pretty_printer
*pp
) const
71 pp_printf (pp
, "extrinsic_state: %i checker(s)\n", get_num_checkers ());
73 state_machine
*checker
;
74 FOR_EACH_VEC_ELT (m_checkers
, i
, checker
)
76 pp_printf (pp
, "m_checkers[%i]: %qs\n", i
, checker
->get_name ());
77 checker
->dump_to_pp (pp
);
81 /* Dump a multiline representation of this state to OUTF. */
84 extrinsic_state::dump_to_file (FILE *outf
) const
88 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
89 pp
.set_output_stream (outf
);
94 /* Dump a multiline representation of this state to stderr. */
97 extrinsic_state::dump () const
99 dump_to_file (stderr
);
102 /* Return a new json::object of the form
103 {"checkers" : array of objects, one for each state_machine}. */
106 extrinsic_state::to_json () const
108 json::object
*ext_state_obj
= new json::object ();
111 json::array
*checkers_arr
= new json::array ();
114 FOR_EACH_VEC_ELT (m_checkers
, i
, sm
)
115 checkers_arr
->append (sm
->to_json ());
116 ext_state_obj
->set ("checkers", checkers_arr
);
119 return ext_state_obj
;
122 /* Get the region_model_manager for this extrinsic_state. */
124 region_model_manager
*
125 extrinsic_state::get_model_manager () const
128 return m_engine
->get_model_manager ();
130 return NULL
; /* for selftests. */
133 /* Try to find a state machine named NAME.
134 If found, return true and write its index to *OUT.
135 Otherwise return false. */
138 extrinsic_state::get_sm_idx_by_name (const char *name
, unsigned *out
) const
142 FOR_EACH_VEC_ELT (m_checkers
, i
, sm
)
143 if (0 == strcmp (name
, sm
->get_name ()))
150 /* NAME not found. */
154 /* struct sm_state_map::entry_t. */
157 sm_state_map::entry_t::cmp (const entry_t
&entry_a
, const entry_t
&entry_b
)
159 gcc_assert (entry_a
.m_state
);
160 gcc_assert (entry_b
.m_state
);
161 if (int cmp_state
= ((int)entry_a
.m_state
->get_id ()
162 - (int)entry_b
.m_state
->get_id ()))
164 if (entry_a
.m_origin
&& entry_b
.m_origin
)
165 return svalue::cmp_ptr (entry_a
.m_origin
, entry_b
.m_origin
);
166 if (entry_a
.m_origin
)
168 if (entry_b
.m_origin
)
173 /* class sm_state_map. */
175 /* sm_state_map's ctor. */
177 sm_state_map::sm_state_map (const state_machine
&sm
)
178 : m_sm (sm
), m_map (), m_global_state (sm
.get_start_state ())
182 /* Clone the sm_state_map. */
185 sm_state_map::clone () const
187 return new sm_state_map (*this);
190 /* Print this sm_state_map to PP.
191 If MODEL is non-NULL, print representative tree values where
195 sm_state_map::print (const region_model
*model
,
196 bool simple
, bool multiline
,
197 pretty_printer
*pp
) const
202 if (m_global_state
!= m_sm
.get_start_state ())
206 pp_string (pp
, "global: ");
207 m_global_state
->dump_to_pp (pp
);
212 auto_vec
<const svalue
*> keys (m_map
.elements ());
213 for (map_t::iterator iter
= m_map
.begin ();
214 iter
!= m_map
.end ();
216 keys
.quick_push ((*iter
).first
);
217 keys
.qsort (svalue::cmp_ptr_ptr
);
220 FOR_EACH_VEC_ELT (keys
, i
, sval
)
225 pp_string (pp
, ", ");
227 if (!flag_dump_noaddr
)
229 pp_pointer (pp
, sval
);
230 pp_string (pp
, ": ");
232 sval
->dump_to_pp (pp
, simple
);
234 entry_t e
= *const_cast <map_t
&> (m_map
).get (sval
);
235 pp_string (pp
, ": ");
236 e
.m_state
->dump_to_pp (pp
);
238 if (tree rep
= model
->get_representative_tree (sval
))
240 pp_string (pp
, " (");
241 dump_quoted_tree (pp
, rep
);
242 pp_character (pp
, ')');
246 pp_string (pp
, " (origin: ");
247 if (!flag_dump_noaddr
)
249 pp_pointer (pp
, e
.m_origin
);
250 pp_string (pp
, ": ");
252 e
.m_origin
->dump_to_pp (pp
, simple
);
254 if (tree rep
= model
->get_representative_tree (e
.m_origin
))
256 pp_string (pp
, " (");
257 dump_quoted_tree (pp
, rep
);
258 pp_character (pp
, ')');
269 /* Dump this object to stderr. */
272 sm_state_map::dump (bool simple
) const
275 pp_format_decoder (&pp
) = default_tree_printer
;
276 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
277 pp
.set_output_stream (stderr
);
278 print (NULL
, simple
, true, &pp
);
283 /* Return a new json::object of the form
284 {"global" : (optional) value for global state,
285 SVAL_DESC : value for state}. */
288 sm_state_map::to_json () const
290 json::object
*map_obj
= new json::object ();
292 if (m_global_state
!= m_sm
.get_start_state ())
293 map_obj
->set ("global", m_global_state
->to_json ());
294 for (map_t::iterator iter
= m_map
.begin ();
295 iter
!= m_map
.end ();
298 const svalue
*sval
= (*iter
).first
;
299 entry_t e
= (*iter
).second
;
301 label_text sval_desc
= sval
->get_desc ();
302 map_obj
->set (sval_desc
.get (), e
.m_state
->to_json ());
304 /* This doesn't yet JSONify e.m_origin. */
309 /* Make a text_art::tree_widget describing this sm_state_map,
310 using MODEL if non-null to describe svalues. */
312 std::unique_ptr
<text_art::widget
>
313 sm_state_map::make_dump_widget (const text_art::dump_widget_info
&dwi
,
314 const region_model
*model
) const
316 using text_art::styled_string
;
317 using text_art::tree_widget
;
318 std::unique_ptr
<tree_widget
> state_widget
319 (tree_widget::from_fmt (dwi
, nullptr,
320 "%qs state machine", m_sm
.get_name ()));
322 if (m_global_state
!= m_sm
.get_start_state ())
324 pretty_printer the_pp
;
325 pretty_printer
* const pp
= &the_pp
;
326 pp_format_decoder (pp
) = default_tree_printer
;
327 pp_string (pp
, "Global State: ");
328 m_global_state
->dump_to_pp (pp
);
329 state_widget
->add_child (tree_widget::make (dwi
, pp
));
332 auto_vec
<const svalue
*> keys (m_map
.elements ());
333 for (map_t::iterator iter
= m_map
.begin ();
334 iter
!= m_map
.end ();
336 keys
.quick_push ((*iter
).first
);
337 keys
.qsort (svalue::cmp_ptr_ptr
);
340 FOR_EACH_VEC_ELT (keys
, i
, sval
)
342 pretty_printer the_pp
;
343 pretty_printer
* const pp
= &the_pp
;
344 const bool simple
= true;
345 pp_format_decoder (pp
) = default_tree_printer
;
346 if (!flag_dump_noaddr
)
348 pp_pointer (pp
, sval
);
349 pp_string (pp
, ": ");
351 sval
->dump_to_pp (pp
, simple
);
353 entry_t e
= *const_cast <map_t
&> (m_map
).get (sval
);
354 pp_string (pp
, ": ");
355 e
.m_state
->dump_to_pp (pp
);
357 if (tree rep
= model
->get_representative_tree (sval
))
359 pp_string (pp
, " (");
360 dump_quoted_tree (pp
, rep
);
361 pp_character (pp
, ')');
365 pp_string (pp
, " (origin: ");
366 if (!flag_dump_noaddr
)
368 pp_pointer (pp
, e
.m_origin
);
369 pp_string (pp
, ": ");
371 e
.m_origin
->dump_to_pp (pp
, simple
);
373 if (tree rep
= model
->get_representative_tree (e
.m_origin
))
375 pp_string (pp
, " (");
376 dump_quoted_tree (pp
, rep
);
377 pp_character (pp
, ')');
382 state_widget
->add_child (tree_widget::make (dwi
, pp
));
385 return std::move (state_widget
);
388 /* Return true if no states have been set within this map
389 (all expressions are for the start state). */
392 sm_state_map::is_empty_p () const
394 return m_map
.elements () == 0 && m_global_state
== m_sm
.get_start_state ();
397 /* Generate a hash value for this sm_state_map. */
400 sm_state_map::hash () const
402 hashval_t result
= 0;
404 /* Accumulate the result by xoring a hash for each slot, so that the
405 result doesn't depend on the ordering of the slots in the map. */
407 for (map_t::iterator iter
= m_map
.begin ();
408 iter
!= m_map
.end ();
411 inchash::hash hstate
;
412 hstate
.add_ptr ((*iter
).first
);
413 entry_t e
= (*iter
).second
;
414 hstate
.add_int (e
.m_state
->get_id ());
415 hstate
.add_ptr (e
.m_origin
);
416 result
^= hstate
.end ();
418 result
^= m_global_state
->get_id ();
423 /* Equality operator for sm_state_map. */
426 sm_state_map::operator== (const sm_state_map
&other
) const
428 if (m_global_state
!= other
.m_global_state
)
431 if (m_map
.elements () != other
.m_map
.elements ())
434 for (map_t::iterator iter
= m_map
.begin ();
435 iter
!= m_map
.end ();
438 const svalue
*sval
= (*iter
).first
;
439 entry_t e
= (*iter
).second
;
440 entry_t
*other_slot
= const_cast <map_t
&> (other
.m_map
).get (sval
);
441 if (other_slot
== NULL
)
443 if (e
!= *other_slot
)
447 gcc_checking_assert (hash () == other
.hash ());
452 /* Get the state of SVAL within this object.
453 States default to the start state. */
455 state_machine::state_t
456 sm_state_map::get_state (const svalue
*sval
,
457 const extrinsic_state
&ext_state
) const
461 sval
= canonicalize_svalue (sval
, ext_state
);
464 = const_cast <map_t
&> (m_map
).get (sval
))
465 return slot
->m_state
;
467 /* SVAL has no explicit sm-state.
468 If this sm allows for state inheritance, then SVAL might have implicit
469 sm-state inherited via a parent.
470 For example INIT_VAL(foo.field) might inherit taintedness state from
472 if (m_sm
.inherited_state_p ())
473 if (region_model_manager
*mgr
= ext_state
.get_model_manager ())
475 if (const initial_svalue
*init_sval
= sval
->dyn_cast_initial_svalue ())
477 const region
*reg
= init_sval
->get_region ();
478 /* Try recursing upwards (up to the base region for the
480 if (!reg
->base_region_p ())
481 if (const region
*parent_reg
= reg
->get_parent_region ())
483 const svalue
*parent_init_sval
484 = mgr
->get_or_create_initial_value (parent_reg
);
485 state_machine::state_t parent_state
486 = get_state (parent_init_sval
, ext_state
);
491 else if (const sub_svalue
*sub_sval
= sval
->dyn_cast_sub_svalue ())
493 const svalue
*parent_sval
= sub_sval
->get_parent ();
494 if (state_machine::state_t parent_state
495 = get_state (parent_sval
, ext_state
))
500 if (state_machine::state_t state
501 = m_sm
.alt_get_inherited_state (*this, sval
, ext_state
))
504 return m_sm
.get_default_state (sval
);
507 /* Get the "origin" svalue for any state of SVAL. */
510 sm_state_map::get_origin (const svalue
*sval
,
511 const extrinsic_state
&ext_state
) const
515 sval
= canonicalize_svalue (sval
, ext_state
);
518 = const_cast <map_t
&> (m_map
).get (sval
);
520 return slot
->m_origin
;
525 /* Set the state of SID within MODEL to STATE, recording that
526 the state came from ORIGIN. */
529 sm_state_map::set_state (region_model
*model
,
531 state_machine::state_t state
,
532 const svalue
*origin
,
533 const extrinsic_state
&ext_state
)
538 /* Reject attempts to set state on UNKNOWN/POISONED. */
539 if (!sval
->can_have_associated_state_p ())
542 equiv_class
&ec
= model
->get_constraints ()->get_equiv_class (sval
);
543 if (!set_state (ec
, state
, origin
, ext_state
))
547 /* Set the state of EC to STATE, recording that the state came from
549 Return true if any states of svalue_ids within EC changed. */
552 sm_state_map::set_state (const equiv_class
&ec
,
553 state_machine::state_t state
,
554 const svalue
*origin
,
555 const extrinsic_state
&ext_state
)
557 bool any_changed
= false;
558 for (const svalue
*sval
: ec
.m_vars
)
559 any_changed
|= impl_set_state (sval
, state
, origin
, ext_state
);
563 /* Set state of SVAL to STATE, bypassing equivalence classes.
564 Return true if the state changed. */
567 sm_state_map::impl_set_state (const svalue
*sval
,
568 state_machine::state_t state
,
569 const svalue
*origin
,
570 const extrinsic_state
&ext_state
)
572 sval
= canonicalize_svalue (sval
, ext_state
);
574 if (get_state (sval
, ext_state
) == state
)
577 gcc_assert (sval
->can_have_associated_state_p ());
579 if (m_sm
.inherited_state_p ())
581 if (const compound_svalue
*compound_sval
582 = sval
->dyn_cast_compound_svalue ())
583 for (auto iter
: *compound_sval
)
585 const svalue
*inner_sval
= iter
.second
;
586 if (inner_sval
->can_have_associated_state_p ())
587 impl_set_state (inner_sval
, state
, origin
, ext_state
);
591 /* Special-case state 0 as the default value. */
594 if (m_map
.get (sval
))
599 m_map
.put (sval
, entry_t (state
, origin
));
603 /* Clear any state for SVAL from this state map. */
606 sm_state_map::clear_any_state (const svalue
*sval
)
611 /* Clear all per-svalue state within this state map. */
614 sm_state_map::clear_all_per_svalue_state ()
619 /* Set the "global" state within this state map to STATE. */
622 sm_state_map::set_global_state (state_machine::state_t state
)
624 m_global_state
= state
;
627 /* Get the "global" state within this state map. */
629 state_machine::state_t
630 sm_state_map::get_global_state () const
632 return m_global_state
;
635 /* Purge any state for SVAL.
636 If !SM::can_purge_p, then report the state as leaking,
640 sm_state_map::on_svalue_leak (const svalue
*sval
,
641 impl_region_model_context
*ctxt
)
643 if (state_machine::state_t state
= get_state (sval
, ctxt
->m_ext_state
))
645 if (m_sm
.can_purge_p (state
))
648 ctxt
->on_state_leak (m_sm
, sval
, state
);
652 /* Purge any state for svalues that aren't live with respect to LIVE_SVALUES
656 sm_state_map::on_liveness_change (const svalue_set
&live_svalues
,
657 const region_model
*model
,
658 const extrinsic_state
&ext_state
,
659 impl_region_model_context
*ctxt
)
661 svalue_set svals_to_unset
;
662 uncertainty_t
*uncertainty
= ctxt
->get_uncertainty ();
664 auto_vec
<const svalue
*> leaked_svals (m_map
.elements ());
665 for (map_t::iterator iter
= m_map
.begin ();
666 iter
!= m_map
.end ();
669 const svalue
*iter_sval
= (*iter
).first
;
670 if (!iter_sval
->live_p (&live_svalues
, model
))
672 svals_to_unset
.add (iter_sval
);
673 entry_t e
= (*iter
).second
;
674 if (!m_sm
.can_purge_p (e
.m_state
))
675 leaked_svals
.quick_push (iter_sval
);
678 if (uncertainty
->unknown_sm_state_p (iter_sval
))
679 svals_to_unset
.add (iter_sval
);
682 leaked_svals
.qsort (svalue::cmp_ptr_ptr
);
686 FOR_EACH_VEC_ELT (leaked_svals
, i
, sval
)
688 entry_t e
= *m_map
.get (sval
);
689 ctxt
->on_state_leak (m_sm
, sval
, e
.m_state
);
692 sm_state_map old_sm_map
= *this;
694 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
695 iter
!= svals_to_unset
.end (); ++iter
)
696 m_map
.remove (*iter
);
698 /* For state machines like "taint" where states can be
699 alt-inherited from other svalues, ensure that state purging doesn't
700 make us lose sm-state.
707 arr[foo.field].f1 = v1;
709 where the last line is:
711 (A): _t1 = foo.field;
712 (B): _t2 = _t1 * sizeof(arr[0]);
713 (C): [arr + _t2].f1 = val;
715 At (A), foo is 'tainted' and foo.field is 'has_ub'.
716 After (B), foo.field's value (in _t1) is no longer directly
717 within LIVE_SVALUES, so with state purging enabled, we would
718 erroneously purge the "has_ub" state from the svalue.
720 Given that _t2's value's state comes from _t1's value's state,
721 we need to preserve that information.
723 Hence for all svalues that have had their explicit sm-state unset,
724 having their sm-state being unset, determine if doing so has changed
725 their effective state, and if so, explicitly set their state.
727 For example, in the above, unsetting the "has_ub" for _t1's value means
728 that _t2's effective value changes from "has_ub" (from alt-inherited
729 from _t1's value) to "tainted" (inherited from "foo"'s value).
731 For such cases, preserve the effective state by explicitly setting the
732 new state. In the above example, this means explicitly setting _t2's
733 value to the value ("has_ub") it was previously alt-inheriting from _t1's
735 if (m_sm
.has_alt_get_inherited_state_p ())
737 auto_vec
<const svalue
*> svalues_needing_state
;
738 for (auto unset_sval
: svals_to_unset
)
740 const state_machine::state_t old_state
741 = old_sm_map
.get_state (unset_sval
, ext_state
);
742 const state_machine::state_t new_state
743 = get_state (unset_sval
, ext_state
);
744 if (new_state
!= old_state
)
745 svalues_needing_state
.safe_push (unset_sval
);
747 for (auto sval
: svalues_needing_state
)
749 const state_machine::state_t old_state
750 = old_sm_map
.get_state (sval
, ext_state
);
751 impl_set_state (sval
, old_state
, nullptr, ext_state
);
756 /* Purge state from SVAL (in response to a call to an unknown function). */
759 sm_state_map::on_unknown_change (const svalue
*sval
,
761 const extrinsic_state
&ext_state
)
763 svalue_set svals_to_unset
;
765 for (map_t::iterator iter
= m_map
.begin ();
766 iter
!= m_map
.end ();
769 const svalue
*key
= (*iter
).first
;
770 entry_t e
= (*iter
).second
;
771 /* We only want to purge state for some states when things
772 are mutable. For example, in sm-malloc.cc, an on-stack ptr
773 doesn't stop being stack-allocated when passed to an unknown fn. */
774 if (!m_sm
.reset_when_passed_to_unknown_fn_p (e
.m_state
, is_mutable
))
777 svals_to_unset
.add (key
);
778 /* If we have INIT_VAL(BASE_REG), then unset any INIT_VAL(REG)
779 for REG within BASE_REG. */
780 if (const initial_svalue
*init_sval
= sval
->dyn_cast_initial_svalue ())
781 if (const initial_svalue
*init_key
= key
->dyn_cast_initial_svalue ())
783 const region
*changed_reg
= init_sval
->get_region ();
784 const region
*changed_key
= init_key
->get_region ();
785 if (changed_key
->get_base_region () == changed_reg
)
786 svals_to_unset
.add (key
);
790 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
791 iter
!= svals_to_unset
.end (); ++iter
)
792 impl_set_state (*iter
, (state_machine::state_t
)0, NULL
, ext_state
);
795 /* Purge state for things involving SVAL.
796 For use when SVAL changes meaning, at the def_stmt on an SSA_NAME. */
799 sm_state_map::purge_state_involving (const svalue
*sval
,
800 const extrinsic_state
&ext_state
)
802 /* Currently svalue::involves_p requires this. */
803 if (!(sval
->get_kind () == SK_INITIAL
804 || sval
->get_kind () == SK_CONJURED
))
807 svalue_set svals_to_unset
;
809 for (map_t::iterator iter
= m_map
.begin ();
810 iter
!= m_map
.end ();
813 const svalue
*key
= (*iter
).first
;
814 entry_t e
= (*iter
).second
;
815 if (!m_sm
.can_purge_p (e
.m_state
))
817 if (key
->involves_p (sval
))
818 svals_to_unset
.add (key
);
821 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
822 iter
!= svals_to_unset
.end (); ++iter
)
823 impl_set_state (*iter
, (state_machine::state_t
)0, NULL
, ext_state
);
826 /* Comparator for imposing an order on sm_state_map instances. */
829 sm_state_map::cmp (const sm_state_map
&smap_a
, const sm_state_map
&smap_b
)
831 if (int cmp_count
= smap_a
.elements () - smap_b
.elements ())
834 auto_vec
<const svalue
*> keys_a (smap_a
.elements ());
835 for (map_t::iterator iter
= smap_a
.begin ();
836 iter
!= smap_a
.end ();
838 keys_a
.quick_push ((*iter
).first
);
839 keys_a
.qsort (svalue::cmp_ptr_ptr
);
841 auto_vec
<const svalue
*> keys_b (smap_b
.elements ());
842 for (map_t::iterator iter
= smap_b
.begin ();
843 iter
!= smap_b
.end ();
845 keys_b
.quick_push ((*iter
).first
);
846 keys_b
.qsort (svalue::cmp_ptr_ptr
);
849 const svalue
*sval_a
;
850 FOR_EACH_VEC_ELT (keys_a
, i
, sval_a
)
852 const svalue
*sval_b
= keys_b
[i
];
853 if (int cmp_sval
= svalue::cmp_ptr (sval_a
, sval_b
))
855 const entry_t
*e_a
= const_cast <map_t
&> (smap_a
.m_map
).get (sval_a
);
856 const entry_t
*e_b
= const_cast <map_t
&> (smap_b
.m_map
).get (sval_b
);
857 if (int cmp_entry
= entry_t::cmp (*e_a
, *e_b
))
864 /* Canonicalize SVAL before getting/setting it within the map.
865 Convert all NULL pointers to (void *) to avoid state explosions
866 involving all of the various (foo *)NULL vs (bar *)NULL. */
869 sm_state_map::canonicalize_svalue (const svalue
*sval
,
870 const extrinsic_state
&ext_state
)
872 region_model_manager
*mgr
= ext_state
.get_model_manager ();
873 if (mgr
&& sval
->get_type () && POINTER_TYPE_P (sval
->get_type ()))
874 if (tree cst
= sval
->maybe_get_constant ())
876 return mgr
->get_or_create_constant_svalue (null_pointer_node
);
881 /* Attempt to merge this state map with OTHER, writing the result
883 Return true if the merger was possible, false otherwise.
885 Normally, only identical state maps can be merged, so that
886 differences between state maps lead to different enodes
888 However some state machines may support merging states to
889 allow for discarding of less important states, and thus avoid
890 blow-up of the exploded graph. */
893 sm_state_map::can_merge_with_p (const sm_state_map
&other
,
894 const state_machine
&sm
,
895 const extrinsic_state
&ext_state
,
896 sm_state_map
**out
) const
898 /* If identical, then they merge trivially, with a copy. */
907 *out
= new sm_state_map (sm
);
909 /* Otherwise, attempt to merge element by element. */
911 /* Try to merge global state. */
912 if (state_machine::state_t merged_global_state
913 = sm
.maybe_get_merged_state (get_global_state (),
914 other
.get_global_state ()))
915 (*out
)->set_global_state (merged_global_state
);
919 /* Try to merge state each svalue's state (for the union
920 of svalues represented by each smap).
921 Ignore the origin information. */
922 hash_set
<const svalue
*> svals
;
923 for (auto kv
: *this)
924 svals
.add (kv
.first
);
925 for (auto kv
: other
)
926 svals
.add (kv
.first
);
927 for (auto sval
: svals
)
929 state_machine::state_t this_state
= get_state (sval
, ext_state
);
930 state_machine::state_t other_state
= other
.get_state (sval
, ext_state
);
931 if (state_machine::state_t merged_state
932 = sm
.maybe_get_merged_state (this_state
, other_state
))
933 (*out
)->impl_set_state (sval
, merged_state
, NULL
, ext_state
);
938 /* Successfully merged all elements. */
942 /* class program_state. */
944 /* program_state's ctor. */
946 program_state::program_state (const extrinsic_state
&ext_state
)
947 : m_region_model (NULL
),
948 m_checker_states (ext_state
.get_num_checkers ()),
951 engine
*eng
= ext_state
.get_engine ();
952 region_model_manager
*mgr
= eng
->get_model_manager ();
953 m_region_model
= new region_model (mgr
);
954 const int num_states
= ext_state
.get_num_checkers ();
955 for (int i
= 0; i
< num_states
; i
++)
957 sm_state_map
*sm
= new sm_state_map (ext_state
.get_sm (i
));
958 m_checker_states
.quick_push (sm
);
962 /* Attempt to use R to replay SUMMARY into this object.
963 Return true if it is possible. */
966 sm_state_map::replay_call_summary (call_summary_replay
&r
,
967 const sm_state_map
&summary
)
969 for (auto kv
: summary
.m_map
)
971 const svalue
*summary_sval
= kv
.first
;
972 const svalue
*caller_sval
= r
.convert_svalue_from_summary (summary_sval
);
975 if (!caller_sval
->can_have_associated_state_p ())
977 const svalue
*summary_origin
= kv
.second
.m_origin
;
978 const svalue
*caller_origin
980 ? r
.convert_svalue_from_summary (summary_origin
)
982 // caller_origin can be NULL.
983 m_map
.put (caller_sval
, entry_t (kv
.second
.m_state
, caller_origin
));
985 m_global_state
= summary
.m_global_state
;
989 /* program_state's copy ctor. */
991 program_state::program_state (const program_state
&other
)
992 : m_region_model (new region_model (*other
.m_region_model
)),
993 m_checker_states (other
.m_checker_states
.length ()),
998 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
999 m_checker_states
.quick_push (smap
->clone ());
1002 /* program_state's assignment operator. */
1005 program_state::operator= (const program_state
&other
)
1007 delete m_region_model
;
1008 m_region_model
= new region_model (*other
.m_region_model
);
1012 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
1014 m_checker_states
.truncate (0);
1015 gcc_assert (m_checker_states
.space (other
.m_checker_states
.length ()));
1017 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
1018 m_checker_states
.quick_push (smap
->clone ());
1020 m_valid
= other
.m_valid
;
1025 /* Move constructor for program_state (when building with C++11). */
1026 program_state::program_state (program_state
&&other
)
1027 : m_region_model (other
.m_region_model
),
1028 m_checker_states (other
.m_checker_states
.length ())
1030 other
.m_region_model
= NULL
;
1034 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
1035 m_checker_states
.quick_push (smap
);
1036 other
.m_checker_states
.truncate (0);
1038 m_valid
= other
.m_valid
;
1041 /* program_state's dtor. */
1043 program_state::~program_state ()
1045 delete m_region_model
;
1048 /* Generate a hash value for this program_state. */
1051 program_state::hash () const
1053 hashval_t result
= m_region_model
->hash ();
1057 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
1058 result
^= smap
->hash ();
1062 /* Equality operator for program_state.
1063 All parts of the program_state (region model, checker states) must
1064 equal their counterparts in OTHER for the two program_states to be
1065 considered equal. */
1068 program_state::operator== (const program_state
&other
) const
1070 if (!(*m_region_model
== *other
.m_region_model
))
1075 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
1076 if (!(*smap
== *other
.m_checker_states
[i
]))
1079 gcc_checking_assert (hash () == other
.hash ());
1084 /* Print a compact representation of this state to PP. */
1087 program_state::print (const extrinsic_state
&ext_state
,
1088 pretty_printer
*pp
) const
1090 pp_printf (pp
, "rmodel: ");
1091 m_region_model
->dump_to_pp (pp
, true, false);
1096 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
1098 if (!smap
->is_empty_p ())
1100 pp_printf (pp
, "%s: ", ext_state
.get_name (i
));
1101 smap
->print (m_region_model
, true, false, pp
);
1107 pp_printf (pp
, "invalid state");
1112 /* Dump a representation of this state to PP. */
1115 program_state::dump_to_pp (const extrinsic_state
&ext_state
,
1116 bool /*summarize*/, bool multiline
,
1117 pretty_printer
*pp
) const
1120 pp_string (pp
, "{");
1122 pp_printf (pp
, "rmodel:");
1126 pp_string (pp
, " {");
1127 m_region_model
->dump_to_pp (pp
, true, multiline
);
1129 pp_string (pp
, "}");
1134 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
1136 if (!smap
->is_empty_p ())
1139 pp_string (pp
, " {");
1140 pp_printf (pp
, "%s: ", ext_state
.get_name (i
));
1143 smap
->print (m_region_model
, true, multiline
, pp
);
1145 pp_string (pp
, "}");
1153 pp_printf (pp
, "invalid state");
1158 pp_string (pp
, "}");
1161 /* Dump a representation of this state to OUTF. */
1164 program_state::dump_to_file (const extrinsic_state
&ext_state
,
1165 bool summarize
, bool multiline
,
1169 pp_format_decoder (&pp
) = default_tree_printer
;
1171 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
1172 pp
.set_output_stream (outf
);
1173 dump_to_pp (ext_state
, summarize
, multiline
, &pp
);
1177 /* Dump a multiline representation of this state to stderr. */
1180 program_state::dump (const extrinsic_state
&ext_state
,
1181 bool summarize
) const
1183 dump_to_file (ext_state
, summarize
, true, stderr
);
1186 /* Dump a tree-like representation of this state to stderr. */
1189 program_state::dump () const
1191 text_art::dump (*this);
1194 /* Return a new json::object of the form
1195 {"store" : object for store,
1196 "constraints" : object for constraint_manager,
1197 "curr_frame" : (optional) str for current frame,
1198 "checkers" : { STATE_NAME : object per sm_state_map },
1199 "valid" : true/false}. */
1202 program_state::to_json (const extrinsic_state
&ext_state
) const
1204 json::object
*state_obj
= new json::object ();
1206 state_obj
->set ("store", m_region_model
->get_store ()->to_json ());
1207 state_obj
->set ("constraints",
1208 m_region_model
->get_constraints ()->to_json ());
1209 if (m_region_model
->get_current_frame ())
1210 state_obj
->set ("curr_frame",
1211 m_region_model
->get_current_frame ()->to_json ());
1213 /* Provide m_checker_states as an object, using names as keys. */
1215 json::object
*checkers_obj
= new json::object ();
1219 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
1220 if (!smap
->is_empty_p ())
1221 checkers_obj
->set (ext_state
.get_name (i
), smap
->to_json ());
1223 state_obj
->set ("checkers", checkers_obj
);
1226 state_obj
->set ("valid", new json::literal (m_valid
));
1232 std::unique_ptr
<text_art::widget
>
1233 program_state::make_dump_widget (const text_art::dump_widget_info
&dwi
) const
1235 using text_art::tree_widget
;
1236 std::unique_ptr
<tree_widget
> state_widget
1237 (tree_widget::from_fmt (dwi
, nullptr, "State"));
1239 state_widget
->add_child (m_region_model
->make_dump_widget (dwi
));
1241 /* Add nodes for any sm_state_maps with state. */
1245 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
1246 if (!smap
->is_empty_p ())
1247 state_widget
->add_child (smap
->make_dump_widget (dwi
, m_region_model
));
1250 return std::move (state_widget
);
1253 /* Update this program_state to reflect a top-level call to FUN.
1254 The params will have initial_svalues. */
1257 program_state::push_frame (const extrinsic_state
&ext_state ATTRIBUTE_UNUSED
,
1258 const function
&fun
)
1260 m_region_model
->push_frame (fun
, NULL
, NULL
);
1263 /* Get the current function of this state. */
1266 program_state::get_current_function () const
1268 return m_region_model
->get_current_function ();
1271 /* Determine if following edge SUCC from ENODE is valid within the graph EG
1272 and update this state accordingly in-place.
1274 Return true if the edge can be followed, or false otherwise.
1276 Check for relevant conditionals and switch-values for conditionals
1277 and switch statements, adding the relevant conditions to this state.
1278 Push/pop frames for interprocedural edges and update params/returned
1281 This is the "state" half of exploded_node::on_edge. */
1284 program_state::on_edge (exploded_graph
&eg
,
1285 exploded_node
*enode
,
1286 const superedge
*succ
,
1287 uncertainty_t
*uncertainty
)
1289 class my_path_context
: public path_context
1292 my_path_context (bool &terminated
) : m_terminated (terminated
) {}
1293 void bifurcate (std::unique_ptr
<custom_edge_info
>) final override
1298 void terminate_path () final override
1300 m_terminated
= true;
1303 bool terminate_path_p () const final override
1305 return m_terminated
;
1311 const program_point
&point
= enode
->get_point ();
1312 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1314 /* For conditionals and switch statements, add the
1315 relevant conditions (for the specific edge) to new_state;
1316 skip edges for which the resulting constraints
1318 This also updates frame information for call/return superedges.
1319 Adding the relevant conditions for the edge could also trigger
1320 sm-state transitions (e.g. transitions due to ptrs becoming known
1321 to be NULL or non-NULL) */
1322 bool terminated
= false;
1323 my_path_context
path_ctxt (terminated
);
1324 impl_region_model_context
ctxt (eg
, enode
,
1325 &enode
->get_state (),
1327 uncertainty
, &path_ctxt
,
1329 std::unique_ptr
<rejected_constraint
> rc
;
1330 logger
* const logger
= eg
.get_logger ();
1331 if (!m_region_model
->maybe_update_for_edge (*succ
,
1334 logger
? &rc
: nullptr))
1338 logger
->start_log_line ();
1339 logger
->log_partial ("edge to SN: %i is impossible"
1340 " due to region_model constraint: ",
1341 succ
->m_dest
->m_index
);
1342 rc
->dump_to_pp (logger
->get_printer ());
1343 logger
->end_log_line ();
1350 program_state::detect_leaks (enode
->get_state (), *this,
1351 NULL
, eg
.get_ext_state (),
1357 /* Update this program_state to reflect a call to function
1358 represented by CALL_STMT.
1359 currently used only when the call doesn't have a superedge representing
1360 the call ( like call via a function pointer ) */
1362 program_state::push_call (exploded_graph
&eg
,
1363 exploded_node
*enode
,
1364 const gcall
*call_stmt
,
1365 uncertainty_t
*uncertainty
)
1368 const program_point
&point
= enode
->get_point ();
1369 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1371 impl_region_model_context
ctxt (eg
, enode
,
1372 &enode
->get_state (),
1377 m_region_model
->update_for_gcall (call_stmt
, &ctxt
);
1380 /* Update this program_state to reflect a return from function
1381 call to which is represented by CALL_STMT.
1382 currently used only when the call doesn't have a superedge representing
1385 program_state::returning_call (exploded_graph
&eg
,
1386 exploded_node
*enode
,
1387 const gcall
*call_stmt
,
1388 uncertainty_t
*uncertainty
)
1391 const program_point
&point
= enode
->get_point ();
1392 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1394 impl_region_model_context
ctxt (eg
, enode
,
1395 &enode
->get_state (),
1400 m_region_model
->update_for_return_gcall (call_stmt
, &ctxt
);
1403 /* Generate a simpler version of THIS, discarding state that's no longer
1405 The idea is that we're more likely to be able to consolidate
1406 multiple (point, state) into single exploded_nodes if we discard
1407 irrelevant state (e.g. at the end of functions). */
1410 program_state::prune_for_point (exploded_graph
&eg
,
1411 const program_point
&point
,
1412 exploded_node
*enode_for_diag
,
1413 uncertainty_t
*uncertainty
) const
1415 logger
* const logger
= eg
.get_logger ();
1418 function
*fun
= point
.get_function ();
1422 program_state
new_state (*this);
1424 const state_purge_map
*pm
= eg
.get_purge_map ();
1427 unsigned num_ssas_purged
= 0;
1428 unsigned num_decls_purged
= 0;
1429 auto_vec
<const decl_region
*> regs
;
1430 new_state
.m_region_model
->get_regions_for_current_frame (®s
);
1431 regs
.qsort (region::cmp_ptr_ptr
);
1433 const decl_region
*reg
;
1434 FOR_EACH_VEC_ELT (regs
, i
, reg
)
1436 const tree node
= reg
->get_decl ();
1437 if (TREE_CODE (node
) == SSA_NAME
)
1439 const tree ssa_name
= node
;
1440 const state_purge_per_ssa_name
&per_ssa
1441 = pm
->get_data_for_ssa_name (node
);
1442 if (!per_ssa
.needed_at_point_p (point
.get_function_point ()))
1444 /* Don't purge bindings of SSA names to svalues
1445 that have unpurgable sm-state, so that leaks are
1446 reported at the end of the function, rather than
1447 at the last place that such an SSA name is referred to.
1449 But do purge them for temporaries (when SSA_NAME_VAR is
1450 NULL), so that we report for cases where a leak happens when
1451 a variable is overwritten with another value, so that the leak
1452 is reported at the point of overwrite, rather than having
1453 temporaries keep the value reachable until the frame is
1456 = new_state
.m_region_model
->get_store_value (reg
, NULL
);
1457 if (!new_state
.can_purge_p (eg
.get_ext_state (), sval
)
1458 && SSA_NAME_VAR (ssa_name
))
1460 /* (currently only state maps can keep things
1463 logger
->log ("not purging binding for %qE"
1464 " (used by state map)", ssa_name
);
1468 new_state
.m_region_model
->purge_region (reg
);
1474 const tree decl
= node
;
1475 gcc_assert (TREE_CODE (node
) == VAR_DECL
1476 || TREE_CODE (node
) == PARM_DECL
1477 || TREE_CODE (node
) == RESULT_DECL
);
1478 if (const state_purge_per_decl
*per_decl
1479 = pm
->get_any_data_for_decl (decl
))
1480 if (!per_decl
->needed_at_point_p (point
.get_function_point ()))
1482 /* Don't purge bindings of decls if there are svalues
1483 that have unpurgable sm-state within the decl's cluster,
1484 so that leaks are reported at the end of the function,
1485 rather than at the last place that such a decl is
1487 if (!new_state
.can_purge_base_region_p (eg
.get_ext_state (),
1490 /* (currently only state maps can keep things
1493 logger
->log ("not purging binding for %qE"
1494 " (value in binding used by state map)",
1499 new_state
.m_region_model
->purge_region (reg
);
1505 if (num_ssas_purged
> 0 || num_decls_purged
> 0)
1509 logger
->log ("num_ssas_purged: %i", num_ssas_purged
);
1510 logger
->log ("num_decl_purged: %i", num_decls_purged
);
1512 impl_region_model_context
ctxt (eg
, enode_for_diag
,
1517 detect_leaks (*this, new_state
, NULL
, eg
.get_ext_state (), &ctxt
);
1521 new_state
.m_region_model
->canonicalize ();
1526 /* Return true if there are no unpurgeable bindings within BASE_REG. */
1529 program_state::can_purge_base_region_p (const extrinsic_state
&ext_state
,
1530 const region
*base_reg
) const
1532 binding_cluster
*cluster
1533 = m_region_model
->get_store ()->get_cluster (base_reg
);
1537 for (auto iter
: *cluster
)
1539 const svalue
*sval
= iter
.second
;
1540 if (!can_purge_p (ext_state
, sval
))
1547 /* Get a representative tree to use for describing SVAL. */
1550 program_state::get_representative_tree (const svalue
*sval
) const
1552 gcc_assert (m_region_model
);
1553 return m_region_model
->get_representative_tree (sval
);
1556 /* Attempt to merge this state with OTHER, both at POINT.
1557 Write the result to *OUT.
1558 If the states were merged successfully, return true. */
1561 program_state::can_merge_with_p (const program_state
&other
,
1562 const extrinsic_state
&ext_state
,
1563 const program_point
&point
,
1564 program_state
*out
) const
1567 gcc_assert (m_region_model
);
1569 /* Attempt to merge the sm-states. */
1572 FOR_EACH_VEC_ELT (out
->m_checker_states
, i
, smap
)
1573 if (!m_checker_states
[i
]->can_merge_with_p (*other
.m_checker_states
[i
],
1574 ext_state
.get_sm (i
),
1576 &out
->m_checker_states
[i
]))
1579 /* Attempt to merge the region_models. */
1580 if (!m_region_model
->can_merge_with_p (*other
.m_region_model
,
1582 out
->m_region_model
,
1587 out
->m_region_model
->canonicalize ();
1592 /* Assert that this object is valid. */
1595 program_state::validate (const extrinsic_state
&ext_state
) const
1597 /* Skip this in a release build. */
1602 gcc_assert (m_checker_states
.length () == ext_state
.get_num_checkers ());
1603 m_region_model
->validate ();
1607 log_set_of_svalues (logger
*logger
, const char *name
,
1608 const svalue_set
&set
)
1611 logger
->inc_indent ();
1612 auto_vec
<const svalue
*> sval_vecs (set
.elements ());
1613 for (svalue_set::iterator iter
= set
.begin ();
1614 iter
!= set
.end (); ++iter
)
1615 sval_vecs
.quick_push (*iter
);
1616 sval_vecs
.qsort (svalue::cmp_ptr_ptr
);
1619 FOR_EACH_VEC_ELT (sval_vecs
, i
, sval
)
1621 logger
->start_log_line ();
1622 pretty_printer
*pp
= logger
->get_printer ();
1623 if (!flag_dump_noaddr
)
1625 pp_pointer (pp
, sval
);
1626 pp_string (pp
, ": ");
1628 sval
->dump_to_pp (pp
, false);
1629 logger
->end_log_line ();
1631 logger
->dec_indent ();
1634 /* Compare the sets of svalues reachable from each of SRC_STATE and DEST_STATE.
1635 For all svalues that are reachable in SRC_STATE and are not live in
1636 DEST_STATE (whether explicitly reachable in DEST_STATE, or implicitly live
1637 based on the former set), call CTXT->on_svalue_leak for them.
1639 Call on_liveness_change on both the CTXT and on the DEST_STATE's
1640 constraint_manager, purging dead svalues from sm-state and from
1641 constraints, respectively.
1643 This function should be called at each fine-grained state change, not
1644 just at exploded edges. */
1647 program_state::detect_leaks (const program_state
&src_state
,
1648 const program_state
&dest_state
,
1649 const svalue
*extra_sval
,
1650 const extrinsic_state
&ext_state
,
1651 region_model_context
*ctxt
)
1653 logger
*logger
= ext_state
.get_logger ();
1655 const uncertainty_t
*uncertainty
= ctxt
->get_uncertainty ();
1658 pretty_printer
*pp
= logger
->get_printer ();
1659 logger
->start_log_line ();
1660 pp_string (pp
, "src_state: ");
1661 src_state
.dump_to_pp (ext_state
, true, false, pp
);
1662 logger
->end_log_line ();
1663 logger
->start_log_line ();
1664 pp_string (pp
, "dest_state: ");
1665 dest_state
.dump_to_pp (ext_state
, true, false, pp
);
1666 logger
->end_log_line ();
1669 logger
->start_log_line ();
1670 pp_string (pp
, "extra_sval: ");
1671 extra_sval
->dump_to_pp (pp
, true);
1672 logger
->end_log_line ();
1676 logger
->start_log_line ();
1677 pp_string (pp
, "uncertainty: ");
1678 uncertainty
->dump_to_pp (pp
, true);
1679 logger
->end_log_line ();
1683 /* Get svalues reachable from each of src_state and dest_state.
1684 Get svalues *known* to be reachable in src_state.
1685 Pass in uncertainty for dest_state so that we additionally get svalues that
1686 *might* still be reachable in dst_state. */
1687 svalue_set known_src_svalues
;
1688 src_state
.m_region_model
->get_reachable_svalues (&known_src_svalues
,
1690 svalue_set maybe_dest_svalues
;
1691 dest_state
.m_region_model
->get_reachable_svalues (&maybe_dest_svalues
,
1692 extra_sval
, uncertainty
);
1696 log_set_of_svalues (logger
, "src_state known reachable svalues:",
1698 log_set_of_svalues (logger
, "dest_state maybe reachable svalues:",
1699 maybe_dest_svalues
);
1702 auto_vec
<const svalue
*> dead_svals (known_src_svalues
.elements ());
1703 for (svalue_set::iterator iter
= known_src_svalues
.begin ();
1704 iter
!= known_src_svalues
.end (); ++iter
)
1706 const svalue
*sval
= (*iter
);
1707 /* For each sval reachable from SRC_STATE, determine if it is
1708 live in DEST_STATE: either explicitly reachable, implicitly
1709 live based on the set of explicitly reachable svalues,
1710 or possibly reachable as recorded in uncertainty.
1711 Record those that have ceased to be live i.e. were known
1712 to be live, and are now not known to be even possibly-live. */
1713 if (!sval
->live_p (&maybe_dest_svalues
, dest_state
.m_region_model
))
1714 dead_svals
.quick_push (sval
);
1717 /* Call CTXT->on_svalue_leak on all svals in SRC_STATE that have ceased
1718 to be live, sorting them first to ensure deterministic behavior. */
1719 dead_svals
.qsort (svalue::cmp_ptr_ptr
);
1722 FOR_EACH_VEC_ELT (dead_svals
, i
, sval
)
1723 ctxt
->on_svalue_leak (sval
);
1725 /* Purge dead svals from sm-state. */
1726 ctxt
->on_liveness_change (maybe_dest_svalues
,
1727 dest_state
.m_region_model
);
1729 /* Purge dead svals from constraints. */
1730 dest_state
.m_region_model
->get_constraints ()->on_liveness_change
1731 (maybe_dest_svalues
, dest_state
.m_region_model
);
1733 /* Purge dead heap-allocated regions from dynamic extents. */
1734 for (const svalue
*sval
: dead_svals
)
1735 if (const region
*reg
= sval
->maybe_get_region ())
1736 if (reg
->get_kind () == RK_HEAP_ALLOCATED
)
1737 dest_state
.m_region_model
->unset_dynamic_extents (reg
);
1740 /* Attempt to use R to replay SUMMARY into this object.
1741 Return true if it is possible. */
1744 program_state::replay_call_summary (call_summary_replay
&r
,
1745 const program_state
&summary
)
1747 if (!m_region_model
->replay_call_summary (r
, *summary
.m_region_model
))
1750 for (unsigned sm_idx
= 0; sm_idx
< m_checker_states
.length (); sm_idx
++)
1752 const sm_state_map
*summary_sm_map
= summary
.m_checker_states
[sm_idx
];
1753 m_checker_states
[sm_idx
]->replay_call_summary (r
, *summary_sm_map
);
1756 if (!summary
.m_valid
)
1762 /* Handle calls to "__analyzer_dump_state". */
1765 program_state::impl_call_analyzer_dump_state (const gcall
*call
,
1766 const extrinsic_state
&ext_state
,
1767 region_model_context
*ctxt
)
1769 call_details
cd (call
, m_region_model
, ctxt
);
1770 const char *sm_name
= cd
.get_arg_string_literal (0);
1773 error_at (call
->location
, "cannot determine state machine");
1777 if (!ext_state
.get_sm_idx_by_name (sm_name
, &sm_idx
))
1779 error_at (call
->location
, "unrecognized state machine %qs", sm_name
);
1782 const sm_state_map
*smap
= m_checker_states
[sm_idx
];
1784 const svalue
*sval
= cd
.get_arg_svalue (1);
1786 /* Strip off cast to int (due to variadic args). */
1787 if (const svalue
*cast
= sval
->maybe_undo_cast ())
1790 state_machine::state_t state
= smap
->get_state (sval
, ext_state
);
1791 warning_at (call
->location
, 0, "state: %qs", state
->get_name ());
1796 namespace selftest
{
1798 /* Tests for sm_state_map. */
1801 test_sm_state_map ()
1803 tree x
= build_global_decl ("x", integer_type_node
);
1804 tree y
= build_global_decl ("y", integer_type_node
);
1805 tree z
= build_global_decl ("z", integer_type_node
);
1807 state_machine
*sm
= make_malloc_state_machine (NULL
);
1808 auto_delete_vec
<state_machine
> checkers
;
1809 checkers
.safe_push (sm
);
1811 extrinsic_state
ext_state (checkers
, &eng
);
1812 state_machine::state_t start
= sm
->get_start_state ();
1814 /* Test setting states on svalue_id instances directly. */
1816 const state_machine::state
test_state_42 ("test state 42", 42);
1817 const state_machine::state_t TEST_STATE_42
= &test_state_42
;
1818 region_model_manager mgr
;
1819 region_model
model (&mgr
);
1820 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1821 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1822 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1824 sm_state_map
map (*sm
);
1825 ASSERT_TRUE (map
.is_empty_p ());
1826 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1828 map
.impl_set_state (x_sval
, TEST_STATE_42
, z_sval
, ext_state
);
1829 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), TEST_STATE_42
);
1830 ASSERT_EQ (map
.get_origin (x_sval
, ext_state
), z_sval
);
1831 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1832 ASSERT_FALSE (map
.is_empty_p ());
1834 map
.impl_set_state (y_sval
, 0, z_sval
, ext_state
);
1835 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1837 map
.impl_set_state (x_sval
, 0, z_sval
, ext_state
);
1838 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1839 ASSERT_TRUE (map
.is_empty_p ());
1842 const state_machine::state
test_state_5 ("test state 5", 5);
1843 const state_machine::state_t TEST_STATE_5
= &test_state_5
;
1845 /* Test setting states via equivalence classes. */
1847 region_model_manager mgr
;
1848 region_model
model (&mgr
);
1849 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1850 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1851 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1853 sm_state_map
map (*sm
);
1854 ASSERT_TRUE (map
.is_empty_p ());
1855 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1856 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1858 model
.add_constraint (x
, EQ_EXPR
, y
, NULL
);
1860 /* Setting x to a state should also update y, as they
1861 are in the same equivalence class. */
1862 map
.set_state (&model
, x_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1863 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), TEST_STATE_5
);
1864 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), TEST_STATE_5
);
1865 ASSERT_EQ (map
.get_origin (x_sval
, ext_state
), z_sval
);
1866 ASSERT_EQ (map
.get_origin (y_sval
, ext_state
), z_sval
);
1869 /* Test equality and hashing. */
1871 region_model_manager mgr
;
1872 region_model
model (&mgr
);
1873 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1874 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1876 sm_state_map
map0 (*sm
);
1877 sm_state_map
map1 (*sm
);
1878 sm_state_map
map2 (*sm
);
1880 ASSERT_EQ (map0
.hash (), map1
.hash ());
1881 ASSERT_EQ (map0
, map1
);
1883 map1
.impl_set_state (y_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1884 ASSERT_NE (map0
.hash (), map1
.hash ());
1885 ASSERT_NE (map0
, map1
);
1887 /* Make the same change to map2. */
1888 map2
.impl_set_state (y_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1889 ASSERT_EQ (map1
.hash (), map2
.hash ());
1890 ASSERT_EQ (map1
, map2
);
1893 /* Equality and hashing shouldn't depend on ordering. */
1895 const state_machine::state
test_state_2 ("test state 2", 2);
1896 const state_machine::state_t TEST_STATE_2
= &test_state_2
;
1897 const state_machine::state
test_state_3 ("test state 3", 3);
1898 const state_machine::state_t TEST_STATE_3
= &test_state_3
;
1899 sm_state_map
map0 (*sm
);
1900 sm_state_map
map1 (*sm
);
1901 sm_state_map
map2 (*sm
);
1903 ASSERT_EQ (map0
.hash (), map1
.hash ());
1904 ASSERT_EQ (map0
, map1
);
1906 region_model_manager mgr
;
1907 region_model
model (&mgr
);
1908 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1909 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1910 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1912 map1
.impl_set_state (x_sval
, TEST_STATE_2
, NULL
, ext_state
);
1913 map1
.impl_set_state (y_sval
, TEST_STATE_3
, NULL
, ext_state
);
1914 map1
.impl_set_state (z_sval
, TEST_STATE_2
, NULL
, ext_state
);
1916 map2
.impl_set_state (z_sval
, TEST_STATE_2
, NULL
, ext_state
);
1917 map2
.impl_set_state (y_sval
, TEST_STATE_3
, NULL
, ext_state
);
1918 map2
.impl_set_state (x_sval
, TEST_STATE_2
, NULL
, ext_state
);
1920 ASSERT_EQ (map1
.hash (), map2
.hash ());
1921 ASSERT_EQ (map1
, map2
);
1924 // TODO: coverage for purging
1927 /* Check program_state works as expected. */
1930 test_program_state_1 ()
1932 /* Create a program_state for a global ptr "p" that has
1933 malloc sm-state, pointing to a region on the heap. */
1934 tree p
= build_global_decl ("p", ptr_type_node
);
1936 state_machine
*sm
= make_malloc_state_machine (NULL
);
1937 const state_machine::state_t UNCHECKED_STATE
1938 = sm
->get_state_by_name ("unchecked");
1939 auto_delete_vec
<state_machine
> checkers
;
1940 checkers
.safe_push (sm
);
1943 extrinsic_state
ext_state (checkers
, &eng
);
1944 region_model_manager
*mgr
= eng
.get_model_manager ();
1945 program_state
s (ext_state
);
1946 region_model
*model
= s
.m_region_model
;
1947 const svalue
*size_in_bytes
1948 = mgr
->get_or_create_unknown_svalue (size_type_node
);
1949 const region
*new_reg
1950 = model
->get_or_create_region_for_heap_alloc (size_in_bytes
, NULL
);
1951 const svalue
*ptr_sval
= mgr
->get_ptr_svalue (ptr_type_node
, new_reg
);
1952 model
->set_value (model
->get_lvalue (p
, NULL
),
1954 sm_state_map
*smap
= s
.m_checker_states
[0];
1956 smap
->impl_set_state (ptr_sval
, UNCHECKED_STATE
, NULL
, ext_state
);
1957 ASSERT_EQ (smap
->get_state (ptr_sval
, ext_state
), UNCHECKED_STATE
);
1960 /* Check that program_state works for string literals. */
1963 test_program_state_2 ()
1965 /* Create a program_state for a global ptr "p" that points to
1966 a string constant. */
1967 tree p
= build_global_decl ("p", ptr_type_node
);
1969 tree string_cst_ptr
= build_string_literal (4, "foo");
1971 auto_delete_vec
<state_machine
> checkers
;
1973 extrinsic_state
ext_state (checkers
, &eng
);
1975 program_state
s (ext_state
);
1976 region_model
*model
= s
.m_region_model
;
1977 const region
*p_reg
= model
->get_lvalue (p
, NULL
);
1978 const svalue
*str_sval
= model
->get_rvalue (string_cst_ptr
, NULL
);
1979 model
->set_value (p_reg
, str_sval
, NULL
);
1982 /* Verify that program_states with identical sm-state can be merged,
1983 and that the merged program_state preserves the sm-state. */
1986 test_program_state_merging ()
1988 /* Create a program_state for a global ptr "p" that has
1989 malloc sm-state, pointing to a region on the heap. */
1990 tree p
= build_global_decl ("p", ptr_type_node
);
1993 region_model_manager
*mgr
= eng
.get_model_manager ();
1994 program_point
point (program_point::origin (*mgr
));
1995 auto_delete_vec
<state_machine
> checkers
;
1996 checkers
.safe_push (make_malloc_state_machine (NULL
));
1997 extrinsic_state
ext_state (checkers
, &eng
);
1999 program_state
s0 (ext_state
);
2000 uncertainty_t uncertainty
;
2001 impl_region_model_context
ctxt (&s0
, ext_state
, &uncertainty
);
2003 region_model
*model0
= s0
.m_region_model
;
2004 const svalue
*size_in_bytes
2005 = mgr
->get_or_create_unknown_svalue (size_type_node
);
2006 const region
*new_reg
2007 = model0
->get_or_create_region_for_heap_alloc (size_in_bytes
, NULL
);
2008 const svalue
*ptr_sval
= mgr
->get_ptr_svalue (ptr_type_node
, new_reg
);
2009 model0
->set_value (model0
->get_lvalue (p
, &ctxt
),
2011 sm_state_map
*smap
= s0
.m_checker_states
[0];
2012 const state_machine::state
test_state ("test state", 0);
2013 const state_machine::state_t TEST_STATE
= &test_state
;
2014 smap
->impl_set_state (ptr_sval
, TEST_STATE
, NULL
, ext_state
);
2015 ASSERT_EQ (smap
->get_state (ptr_sval
, ext_state
), TEST_STATE
);
2017 model0
->canonicalize ();
2019 /* Verify that canonicalization preserves sm-state. */
2020 ASSERT_EQ (smap
->get_state (model0
->get_rvalue (p
, NULL
), ext_state
),
2023 /* Make a copy of the program_state. */
2024 program_state
s1 (s0
);
2027 /* We have two identical states with "p" pointing to a heap region
2028 with the given sm-state.
2029 They ought to be mergeable, preserving the sm-state. */
2030 program_state
merged (ext_state
);
2031 ASSERT_TRUE (s0
.can_merge_with_p (s1
, ext_state
, point
, &merged
));
2032 merged
.validate (ext_state
);
2034 /* Verify that the merged state has the sm-state for "p". */
2035 region_model
*merged_model
= merged
.m_region_model
;
2036 sm_state_map
*merged_smap
= merged
.m_checker_states
[0];
2037 ASSERT_EQ (merged_smap
->get_state (merged_model
->get_rvalue (p
, NULL
),
2041 /* Try canonicalizing. */
2042 merged
.m_region_model
->canonicalize ();
2043 merged
.validate (ext_state
);
2045 /* Verify that the merged state still has the sm-state for "p". */
2046 ASSERT_EQ (merged_smap
->get_state (merged_model
->get_rvalue (p
, NULL
),
2050 /* After canonicalization, we ought to have equality with the inputs. */
2051 ASSERT_EQ (s0
, merged
);
2054 /* Verify that program_states with different global-state in an sm-state
2058 test_program_state_merging_2 ()
2061 region_model_manager
*mgr
= eng
.get_model_manager ();
2062 program_point
point (program_point::origin (*mgr
));
2063 auto_delete_vec
<state_machine
> checkers
;
2064 checkers
.safe_push (make_signal_state_machine (NULL
));
2065 extrinsic_state
ext_state (checkers
, &eng
);
2067 const state_machine::state
test_state_0 ("test state 0", 0);
2068 const state_machine::state
test_state_1 ("test state 1", 1);
2069 const state_machine::state_t TEST_STATE_0
= &test_state_0
;
2070 const state_machine::state_t TEST_STATE_1
= &test_state_1
;
2072 program_state
s0 (ext_state
);
2074 sm_state_map
*smap0
= s0
.m_checker_states
[0];
2075 smap0
->set_global_state (TEST_STATE_0
);
2076 ASSERT_EQ (smap0
->get_global_state (), TEST_STATE_0
);
2079 program_state
s1 (ext_state
);
2081 sm_state_map
*smap1
= s1
.m_checker_states
[0];
2082 smap1
->set_global_state (TEST_STATE_1
);
2083 ASSERT_EQ (smap1
->get_global_state (), TEST_STATE_1
);
2088 /* They ought to not be mergeable. */
2089 program_state
merged (ext_state
);
2090 ASSERT_FALSE (s0
.can_merge_with_p (s1
, ext_state
, point
, &merged
));
2093 /* Run all of the selftests within this file. */
2096 analyzer_program_state_cc_tests ()
2098 test_sm_state_map ();
2099 test_program_state_1 ();
2100 test_program_state_2 ();
2101 test_program_state_merging ();
2102 test_program_state_merging_2 ();
2105 } // namespace selftest
2107 #endif /* CHECKING_P */
2111 #endif /* #if ENABLE_ANALYZER */