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
24 #include "coretypes.h"
26 #include "diagnostic-core.h"
27 #include "diagnostic.h"
28 #include "analyzer/analyzer.h"
29 #include "analyzer/analyzer-logging.h"
30 #include "analyzer/sm.h"
33 #include "ordered-hash-map.h"
35 #include "analyzer/call-string.h"
36 #include "analyzer/program-point.h"
37 #include "analyzer/store.h"
38 #include "analyzer/region-model.h"
39 #include "analyzer/program-state.h"
40 #include "analyzer/constraint-manager.h"
41 #include "diagnostic-event-id.h"
42 #include "analyzer/pending-diagnostic.h"
43 #include "analyzer/diagnostic-manager.h"
45 #include "basic-block.h"
47 #include "gimple-iterator.h"
50 #include "analyzer/supergraph.h"
51 #include "analyzer/program-state.h"
52 #include "analyzer/exploded-graph.h"
53 #include "analyzer/state-purge.h"
54 #include "analyzer/call-summary.h"
55 #include "analyzer/analyzer-selftests.h"
61 /* class extrinsic_state. */
63 /* Dump a multiline representation of this state to PP. */
66 extrinsic_state::dump_to_pp (pretty_printer
*pp
) const
68 pp_printf (pp
, "extrinsic_state: %i checker(s)\n", get_num_checkers ());
70 state_machine
*checker
;
71 FOR_EACH_VEC_ELT (m_checkers
, i
, checker
)
73 pp_printf (pp
, "m_checkers[%i]: %qs\n", i
, checker
->get_name ());
74 checker
->dump_to_pp (pp
);
78 /* Dump a multiline representation of this state to OUTF. */
81 extrinsic_state::dump_to_file (FILE *outf
) const
85 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
86 pp
.buffer
->stream
= outf
;
91 /* Dump a multiline representation of this state to stderr. */
94 extrinsic_state::dump () const
96 dump_to_file (stderr
);
99 /* Return a new json::object of the form
100 {"checkers" : array of objects, one for each state_machine}. */
103 extrinsic_state::to_json () const
105 json::object
*ext_state_obj
= new json::object ();
108 json::array
*checkers_arr
= new json::array ();
111 FOR_EACH_VEC_ELT (m_checkers
, i
, sm
)
112 checkers_arr
->append (sm
->to_json ());
113 ext_state_obj
->set ("checkers", checkers_arr
);
116 return ext_state_obj
;
119 /* Get the region_model_manager for this extrinsic_state. */
121 region_model_manager
*
122 extrinsic_state::get_model_manager () const
125 return m_engine
->get_model_manager ();
127 return NULL
; /* for selftests. */
130 /* Try to find a state machine named NAME.
131 If found, return true and write its index to *OUT.
132 Otherwise return false. */
135 extrinsic_state::get_sm_idx_by_name (const char *name
, unsigned *out
) const
139 FOR_EACH_VEC_ELT (m_checkers
, i
, sm
)
140 if (0 == strcmp (name
, sm
->get_name ()))
147 /* NAME not found. */
151 /* struct sm_state_map::entry_t. */
154 sm_state_map::entry_t::cmp (const entry_t
&entry_a
, const entry_t
&entry_b
)
156 gcc_assert (entry_a
.m_state
);
157 gcc_assert (entry_b
.m_state
);
158 if (int cmp_state
= ((int)entry_a
.m_state
->get_id ()
159 - (int)entry_b
.m_state
->get_id ()))
161 if (entry_a
.m_origin
&& entry_b
.m_origin
)
162 return svalue::cmp_ptr (entry_a
.m_origin
, entry_b
.m_origin
);
163 if (entry_a
.m_origin
)
165 if (entry_b
.m_origin
)
170 /* class sm_state_map. */
172 /* sm_state_map's ctor. */
174 sm_state_map::sm_state_map (const state_machine
&sm
)
175 : m_sm (sm
), m_map (), m_global_state (sm
.get_start_state ())
179 /* Clone the sm_state_map. */
182 sm_state_map::clone () const
184 return new sm_state_map (*this);
187 /* Print this sm_state_map to PP.
188 If MODEL is non-NULL, print representative tree values where
192 sm_state_map::print (const region_model
*model
,
193 bool simple
, bool multiline
,
194 pretty_printer
*pp
) const
199 if (m_global_state
!= m_sm
.get_start_state ())
203 pp_string (pp
, "global: ");
204 m_global_state
->dump_to_pp (pp
);
209 auto_vec
<const svalue
*> keys (m_map
.elements ());
210 for (map_t::iterator iter
= m_map
.begin ();
211 iter
!= m_map
.end ();
213 keys
.quick_push ((*iter
).first
);
214 keys
.qsort (svalue::cmp_ptr_ptr
);
217 FOR_EACH_VEC_ELT (keys
, i
, sval
)
222 pp_string (pp
, ", ");
224 if (!flag_dump_noaddr
)
226 pp_pointer (pp
, sval
);
227 pp_string (pp
, ": ");
229 sval
->dump_to_pp (pp
, simple
);
231 entry_t e
= *const_cast <map_t
&> (m_map
).get (sval
);
232 pp_string (pp
, ": ");
233 e
.m_state
->dump_to_pp (pp
);
235 if (tree rep
= model
->get_representative_tree (sval
))
237 pp_string (pp
, " (");
238 dump_quoted_tree (pp
, rep
);
239 pp_character (pp
, ')');
243 pp_string (pp
, " (origin: ");
244 if (!flag_dump_noaddr
)
246 pp_pointer (pp
, e
.m_origin
);
247 pp_string (pp
, ": ");
249 e
.m_origin
->dump_to_pp (pp
, simple
);
251 if (tree rep
= model
->get_representative_tree (e
.m_origin
))
253 pp_string (pp
, " (");
254 dump_quoted_tree (pp
, rep
);
255 pp_character (pp
, ')');
266 /* Dump this object to stderr. */
269 sm_state_map::dump (bool simple
) const
272 pp_format_decoder (&pp
) = default_tree_printer
;
273 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
274 pp
.buffer
->stream
= stderr
;
275 print (NULL
, simple
, true, &pp
);
280 /* Return a new json::object of the form
281 {"global" : (optional) value for global state,
282 SVAL_DESC : value for state}. */
285 sm_state_map::to_json () const
287 json::object
*map_obj
= new json::object ();
289 if (m_global_state
!= m_sm
.get_start_state ())
290 map_obj
->set ("global", m_global_state
->to_json ());
291 for (map_t::iterator iter
= m_map
.begin ();
292 iter
!= m_map
.end ();
295 const svalue
*sval
= (*iter
).first
;
296 entry_t e
= (*iter
).second
;
298 label_text sval_desc
= sval
->get_desc ();
299 map_obj
->set (sval_desc
.get (), e
.m_state
->to_json ());
301 /* This doesn't yet JSONify e.m_origin. */
306 /* Return true if no states have been set within this map
307 (all expressions are for the start state). */
310 sm_state_map::is_empty_p () const
312 return m_map
.elements () == 0 && m_global_state
== m_sm
.get_start_state ();
315 /* Generate a hash value for this sm_state_map. */
318 sm_state_map::hash () const
320 hashval_t result
= 0;
322 /* Accumulate the result by xoring a hash for each slot, so that the
323 result doesn't depend on the ordering of the slots in the map. */
325 for (map_t::iterator iter
= m_map
.begin ();
326 iter
!= m_map
.end ();
329 inchash::hash hstate
;
330 hstate
.add_ptr ((*iter
).first
);
331 entry_t e
= (*iter
).second
;
332 hstate
.add_int (e
.m_state
->get_id ());
333 hstate
.add_ptr (e
.m_origin
);
334 result
^= hstate
.end ();
336 result
^= m_global_state
->get_id ();
341 /* Equality operator for sm_state_map. */
344 sm_state_map::operator== (const sm_state_map
&other
) const
346 if (m_global_state
!= other
.m_global_state
)
349 if (m_map
.elements () != other
.m_map
.elements ())
352 for (map_t::iterator iter
= m_map
.begin ();
353 iter
!= m_map
.end ();
356 const svalue
*sval
= (*iter
).first
;
357 entry_t e
= (*iter
).second
;
358 entry_t
*other_slot
= const_cast <map_t
&> (other
.m_map
).get (sval
);
359 if (other_slot
== NULL
)
361 if (e
!= *other_slot
)
365 gcc_checking_assert (hash () == other
.hash ());
370 /* Get the state of SVAL within this object.
371 States default to the start state. */
373 state_machine::state_t
374 sm_state_map::get_state (const svalue
*sval
,
375 const extrinsic_state
&ext_state
) const
379 sval
= canonicalize_svalue (sval
, ext_state
);
382 = const_cast <map_t
&> (m_map
).get (sval
))
383 return slot
->m_state
;
385 /* SVAL has no explicit sm-state.
386 If this sm allows for state inheritance, then SVAL might have implicit
387 sm-state inherited via a parent.
388 For example INIT_VAL(foo.field) might inherit taintedness state from
390 if (m_sm
.inherited_state_p ())
391 if (region_model_manager
*mgr
= ext_state
.get_model_manager ())
393 if (const initial_svalue
*init_sval
= sval
->dyn_cast_initial_svalue ())
395 const region
*reg
= init_sval
->get_region ();
396 /* Try recursing upwards (up to the base region for the
398 if (!reg
->base_region_p ())
399 if (const region
*parent_reg
= reg
->get_parent_region ())
401 const svalue
*parent_init_sval
402 = mgr
->get_or_create_initial_value (parent_reg
);
403 state_machine::state_t parent_state
404 = get_state (parent_init_sval
, ext_state
);
409 else if (const sub_svalue
*sub_sval
= sval
->dyn_cast_sub_svalue ())
411 const svalue
*parent_sval
= sub_sval
->get_parent ();
412 if (state_machine::state_t parent_state
413 = get_state (parent_sval
, ext_state
))
418 if (state_machine::state_t state
419 = m_sm
.alt_get_inherited_state (*this, sval
, ext_state
))
422 return m_sm
.get_default_state (sval
);
425 /* Get the "origin" svalue for any state of SVAL. */
428 sm_state_map::get_origin (const svalue
*sval
,
429 const extrinsic_state
&ext_state
) const
433 sval
= canonicalize_svalue (sval
, ext_state
);
436 = const_cast <map_t
&> (m_map
).get (sval
);
438 return slot
->m_origin
;
443 /* Set the state of SID within MODEL to STATE, recording that
444 the state came from ORIGIN. */
447 sm_state_map::set_state (region_model
*model
,
449 state_machine::state_t state
,
450 const svalue
*origin
,
451 const extrinsic_state
&ext_state
)
456 /* Reject attempts to set state on UNKNOWN/POISONED. */
457 if (!sval
->can_have_associated_state_p ())
460 equiv_class
&ec
= model
->get_constraints ()->get_equiv_class (sval
);
461 if (!set_state (ec
, state
, origin
, ext_state
))
465 /* Set the state of EC to STATE, recording that the state came from
467 Return true if any states of svalue_ids within EC changed. */
470 sm_state_map::set_state (const equiv_class
&ec
,
471 state_machine::state_t state
,
472 const svalue
*origin
,
473 const extrinsic_state
&ext_state
)
475 bool any_changed
= false;
476 for (const svalue
*sval
: ec
.m_vars
)
477 any_changed
|= impl_set_state (sval
, state
, origin
, ext_state
);
481 /* Set state of SVAL to STATE, bypassing equivalence classes.
482 Return true if the state changed. */
485 sm_state_map::impl_set_state (const svalue
*sval
,
486 state_machine::state_t state
,
487 const svalue
*origin
,
488 const extrinsic_state
&ext_state
)
490 sval
= canonicalize_svalue (sval
, ext_state
);
492 if (get_state (sval
, ext_state
) == state
)
495 gcc_assert (sval
->can_have_associated_state_p ());
497 if (m_sm
.inherited_state_p ())
499 if (const compound_svalue
*compound_sval
500 = sval
->dyn_cast_compound_svalue ())
501 for (auto iter
: *compound_sval
)
503 const svalue
*inner_sval
= iter
.second
;
504 if (inner_sval
->can_have_associated_state_p ())
505 impl_set_state (inner_sval
, state
, origin
, ext_state
);
509 /* Special-case state 0 as the default value. */
512 if (m_map
.get (sval
))
517 m_map
.put (sval
, entry_t (state
, origin
));
521 /* Clear any state for SVAL from this state map. */
524 sm_state_map::clear_any_state (const svalue
*sval
)
529 /* Clear all per-svalue state within this state map. */
532 sm_state_map::clear_all_per_svalue_state ()
537 /* Set the "global" state within this state map to STATE. */
540 sm_state_map::set_global_state (state_machine::state_t state
)
542 m_global_state
= state
;
545 /* Get the "global" state within this state map. */
547 state_machine::state_t
548 sm_state_map::get_global_state () const
550 return m_global_state
;
553 /* Purge any state for SVAL.
554 If !SM::can_purge_p, then report the state as leaking,
558 sm_state_map::on_svalue_leak (const svalue
*sval
,
559 impl_region_model_context
*ctxt
)
561 if (state_machine::state_t state
= get_state (sval
, ctxt
->m_ext_state
))
563 if (m_sm
.can_purge_p (state
))
566 ctxt
->on_state_leak (m_sm
, sval
, state
);
570 /* Purge any state for svalues that aren't live with respect to LIVE_SVALUES
574 sm_state_map::on_liveness_change (const svalue_set
&live_svalues
,
575 const region_model
*model
,
576 const extrinsic_state
&ext_state
,
577 impl_region_model_context
*ctxt
)
579 svalue_set svals_to_unset
;
580 uncertainty_t
*uncertainty
= ctxt
->get_uncertainty ();
582 auto_vec
<const svalue
*> leaked_svals (m_map
.elements ());
583 for (map_t::iterator iter
= m_map
.begin ();
584 iter
!= m_map
.end ();
587 const svalue
*iter_sval
= (*iter
).first
;
588 if (!iter_sval
->live_p (&live_svalues
, model
))
590 svals_to_unset
.add (iter_sval
);
591 entry_t e
= (*iter
).second
;
592 if (!m_sm
.can_purge_p (e
.m_state
))
593 leaked_svals
.quick_push (iter_sval
);
596 if (uncertainty
->unknown_sm_state_p (iter_sval
))
597 svals_to_unset
.add (iter_sval
);
600 leaked_svals
.qsort (svalue::cmp_ptr_ptr
);
604 FOR_EACH_VEC_ELT (leaked_svals
, i
, sval
)
606 entry_t e
= *m_map
.get (sval
);
607 ctxt
->on_state_leak (m_sm
, sval
, e
.m_state
);
610 sm_state_map old_sm_map
= *this;
612 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
613 iter
!= svals_to_unset
.end (); ++iter
)
614 m_map
.remove (*iter
);
616 /* For state machines like "taint" where states can be
617 alt-inherited from other svalues, ensure that state purging doesn't
618 make us lose sm-state.
625 arr[foo.field].f1 = v1;
627 where the last line is:
629 (A): _t1 = foo.field;
630 (B): _t2 = _t1 * sizeof(arr[0]);
631 (C): [arr + _t2].f1 = val;
633 At (A), foo is 'tainted' and foo.field is 'has_ub'.
634 After (B), foo.field's value (in _t1) is no longer directly
635 within LIVE_SVALUES, so with state purging enabled, we would
636 erroneously purge the "has_ub" state from the svalue.
638 Given that _t2's value's state comes from _t1's value's state,
639 we need to preserve that information.
641 Hence for all svalues that have had their explicit sm-state unset,
642 having their sm-state being unset, determine if doing so has changed
643 their effective state, and if so, explicitly set their state.
645 For example, in the above, unsetting the "has_ub" for _t1's value means
646 that _t2's effective value changes from "has_ub" (from alt-inherited
647 from _t1's value) to "tainted" (inherited from "foo"'s value).
649 For such cases, preserve the effective state by explicitly setting the
650 new state. In the above example, this means explicitly setting _t2's
651 value to the value ("has_ub") it was previously alt-inheriting from _t1's
653 if (m_sm
.has_alt_get_inherited_state_p ())
655 auto_vec
<const svalue
*> svalues_needing_state
;
656 for (auto unset_sval
: svals_to_unset
)
658 const state_machine::state_t old_state
659 = old_sm_map
.get_state (unset_sval
, ext_state
);
660 const state_machine::state_t new_state
661 = get_state (unset_sval
, ext_state
);
662 if (new_state
!= old_state
)
663 svalues_needing_state
.safe_push (unset_sval
);
665 for (auto sval
: svalues_needing_state
)
667 const state_machine::state_t old_state
668 = old_sm_map
.get_state (sval
, ext_state
);
669 impl_set_state (sval
, old_state
, nullptr, ext_state
);
674 /* Purge state from SVAL (in response to a call to an unknown function). */
677 sm_state_map::on_unknown_change (const svalue
*sval
,
679 const extrinsic_state
&ext_state
)
681 svalue_set svals_to_unset
;
683 for (map_t::iterator iter
= m_map
.begin ();
684 iter
!= m_map
.end ();
687 const svalue
*key
= (*iter
).first
;
688 entry_t e
= (*iter
).second
;
689 /* We only want to purge state for some states when things
690 are mutable. For example, in sm-malloc.cc, an on-stack ptr
691 doesn't stop being stack-allocated when passed to an unknown fn. */
692 if (!m_sm
.reset_when_passed_to_unknown_fn_p (e
.m_state
, is_mutable
))
695 svals_to_unset
.add (key
);
696 /* If we have INIT_VAL(BASE_REG), then unset any INIT_VAL(REG)
697 for REG within BASE_REG. */
698 if (const initial_svalue
*init_sval
= sval
->dyn_cast_initial_svalue ())
699 if (const initial_svalue
*init_key
= key
->dyn_cast_initial_svalue ())
701 const region
*changed_reg
= init_sval
->get_region ();
702 const region
*changed_key
= init_key
->get_region ();
703 if (changed_key
->get_base_region () == changed_reg
)
704 svals_to_unset
.add (key
);
708 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
709 iter
!= svals_to_unset
.end (); ++iter
)
710 impl_set_state (*iter
, (state_machine::state_t
)0, NULL
, ext_state
);
713 /* Purge state for things involving SVAL.
714 For use when SVAL changes meaning, at the def_stmt on an SSA_NAME. */
717 sm_state_map::purge_state_involving (const svalue
*sval
,
718 const extrinsic_state
&ext_state
)
720 /* Currently svalue::involves_p requires this. */
721 if (!(sval
->get_kind () == SK_INITIAL
722 || sval
->get_kind () == SK_CONJURED
))
725 svalue_set svals_to_unset
;
727 for (map_t::iterator iter
= m_map
.begin ();
728 iter
!= m_map
.end ();
731 const svalue
*key
= (*iter
).first
;
732 entry_t e
= (*iter
).second
;
733 if (!m_sm
.can_purge_p (e
.m_state
))
735 if (key
->involves_p (sval
))
736 svals_to_unset
.add (key
);
739 for (svalue_set::iterator iter
= svals_to_unset
.begin ();
740 iter
!= svals_to_unset
.end (); ++iter
)
741 impl_set_state (*iter
, (state_machine::state_t
)0, NULL
, ext_state
);
744 /* Comparator for imposing an order on sm_state_map instances. */
747 sm_state_map::cmp (const sm_state_map
&smap_a
, const sm_state_map
&smap_b
)
749 if (int cmp_count
= smap_a
.elements () - smap_b
.elements ())
752 auto_vec
<const svalue
*> keys_a (smap_a
.elements ());
753 for (map_t::iterator iter
= smap_a
.begin ();
754 iter
!= smap_a
.end ();
756 keys_a
.quick_push ((*iter
).first
);
757 keys_a
.qsort (svalue::cmp_ptr_ptr
);
759 auto_vec
<const svalue
*> keys_b (smap_b
.elements ());
760 for (map_t::iterator iter
= smap_b
.begin ();
761 iter
!= smap_b
.end ();
763 keys_b
.quick_push ((*iter
).first
);
764 keys_b
.qsort (svalue::cmp_ptr_ptr
);
767 const svalue
*sval_a
;
768 FOR_EACH_VEC_ELT (keys_a
, i
, sval_a
)
770 const svalue
*sval_b
= keys_b
[i
];
771 if (int cmp_sval
= svalue::cmp_ptr (sval_a
, sval_b
))
773 const entry_t
*e_a
= const_cast <map_t
&> (smap_a
.m_map
).get (sval_a
);
774 const entry_t
*e_b
= const_cast <map_t
&> (smap_b
.m_map
).get (sval_b
);
775 if (int cmp_entry
= entry_t::cmp (*e_a
, *e_b
))
782 /* Canonicalize SVAL before getting/setting it within the map.
783 Convert all NULL pointers to (void *) to avoid state explosions
784 involving all of the various (foo *)NULL vs (bar *)NULL. */
787 sm_state_map::canonicalize_svalue (const svalue
*sval
,
788 const extrinsic_state
&ext_state
)
790 region_model_manager
*mgr
= ext_state
.get_model_manager ();
791 if (mgr
&& sval
->get_type () && POINTER_TYPE_P (sval
->get_type ()))
792 if (tree cst
= sval
->maybe_get_constant ())
794 return mgr
->get_or_create_constant_svalue (null_pointer_node
);
799 /* Attempt to merge this state map with OTHER, writing the result
801 Return true if the merger was possible, false otherwise.
803 Normally, only identical state maps can be merged, so that
804 differences between state maps lead to different enodes
806 However some state machines may support merging states to
807 allow for discarding of less important states, and thus avoid
808 blow-up of the exploded graph. */
811 sm_state_map::can_merge_with_p (const sm_state_map
&other
,
812 const state_machine
&sm
,
813 const extrinsic_state
&ext_state
,
814 sm_state_map
**out
) const
816 /* If identical, then they merge trivially, with a copy. */
825 *out
= new sm_state_map (sm
);
827 /* Otherwise, attempt to merge element by element. */
829 /* Try to merge global state. */
830 if (state_machine::state_t merged_global_state
831 = sm
.maybe_get_merged_state (get_global_state (),
832 other
.get_global_state ()))
833 (*out
)->set_global_state (merged_global_state
);
837 /* Try to merge state each svalue's state (for the union
838 of svalues represented by each smap).
839 Ignore the origin information. */
840 hash_set
<const svalue
*> svals
;
841 for (auto kv
: *this)
842 svals
.add (kv
.first
);
843 for (auto kv
: other
)
844 svals
.add (kv
.first
);
845 for (auto sval
: svals
)
847 state_machine::state_t this_state
= get_state (sval
, ext_state
);
848 state_machine::state_t other_state
= other
.get_state (sval
, ext_state
);
849 if (state_machine::state_t merged_state
850 = sm
.maybe_get_merged_state (this_state
, other_state
))
851 (*out
)->impl_set_state (sval
, merged_state
, NULL
, ext_state
);
856 /* Successfully merged all elements. */
860 /* class program_state. */
862 /* program_state's ctor. */
864 program_state::program_state (const extrinsic_state
&ext_state
)
865 : m_region_model (NULL
),
866 m_checker_states (ext_state
.get_num_checkers ()),
869 engine
*eng
= ext_state
.get_engine ();
870 region_model_manager
*mgr
= eng
->get_model_manager ();
871 m_region_model
= new region_model (mgr
);
872 const int num_states
= ext_state
.get_num_checkers ();
873 for (int i
= 0; i
< num_states
; i
++)
875 sm_state_map
*sm
= new sm_state_map (ext_state
.get_sm (i
));
876 m_checker_states
.quick_push (sm
);
880 /* Attempt to to use R to replay SUMMARY into this object.
881 Return true if it is possible. */
884 sm_state_map::replay_call_summary (call_summary_replay
&r
,
885 const sm_state_map
&summary
)
887 for (auto kv
: summary
.m_map
)
889 const svalue
*summary_sval
= kv
.first
;
890 const svalue
*caller_sval
= r
.convert_svalue_from_summary (summary_sval
);
893 if (!caller_sval
->can_have_associated_state_p ())
895 const svalue
*summary_origin
= kv
.second
.m_origin
;
896 const svalue
*caller_origin
898 ? r
.convert_svalue_from_summary (summary_origin
)
900 // caller_origin can be NULL.
901 m_map
.put (caller_sval
, entry_t (kv
.second
.m_state
, caller_origin
));
903 m_global_state
= summary
.m_global_state
;
907 /* program_state's copy ctor. */
909 program_state::program_state (const program_state
&other
)
910 : m_region_model (new region_model (*other
.m_region_model
)),
911 m_checker_states (other
.m_checker_states
.length ()),
916 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
917 m_checker_states
.quick_push (smap
->clone ());
920 /* program_state's assignment operator. */
923 program_state::operator= (const program_state
&other
)
925 delete m_region_model
;
926 m_region_model
= new region_model (*other
.m_region_model
);
930 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
932 m_checker_states
.truncate (0);
933 gcc_assert (m_checker_states
.space (other
.m_checker_states
.length ()));
935 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
936 m_checker_states
.quick_push (smap
->clone ());
938 m_valid
= other
.m_valid
;
943 /* Move constructor for program_state (when building with C++11). */
944 program_state::program_state (program_state
&&other
)
945 : m_region_model (other
.m_region_model
),
946 m_checker_states (other
.m_checker_states
.length ())
948 other
.m_region_model
= NULL
;
952 FOR_EACH_VEC_ELT (other
.m_checker_states
, i
, smap
)
953 m_checker_states
.quick_push (smap
);
954 other
.m_checker_states
.truncate (0);
956 m_valid
= other
.m_valid
;
959 /* program_state's dtor. */
961 program_state::~program_state ()
963 delete m_region_model
;
966 /* Generate a hash value for this program_state. */
969 program_state::hash () const
971 hashval_t result
= m_region_model
->hash ();
975 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
976 result
^= smap
->hash ();
980 /* Equality operator for program_state.
981 All parts of the program_state (region model, checker states) must
982 equal their counterparts in OTHER for the two program_states to be
986 program_state::operator== (const program_state
&other
) const
988 if (!(*m_region_model
== *other
.m_region_model
))
993 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
994 if (!(*smap
== *other
.m_checker_states
[i
]))
997 gcc_checking_assert (hash () == other
.hash ());
1002 /* Print a compact representation of this state to PP. */
1005 program_state::print (const extrinsic_state
&ext_state
,
1006 pretty_printer
*pp
) const
1008 pp_printf (pp
, "rmodel: ");
1009 m_region_model
->dump_to_pp (pp
, true, false);
1014 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
1016 if (!smap
->is_empty_p ())
1018 pp_printf (pp
, "%s: ", ext_state
.get_name (i
));
1019 smap
->print (m_region_model
, true, false, pp
);
1025 pp_printf (pp
, "invalid state");
1030 /* Dump a representation of this state to PP. */
1033 program_state::dump_to_pp (const extrinsic_state
&ext_state
,
1034 bool /*summarize*/, bool multiline
,
1035 pretty_printer
*pp
) const
1038 pp_string (pp
, "{");
1040 pp_printf (pp
, "rmodel:");
1044 pp_string (pp
, " {");
1045 m_region_model
->dump_to_pp (pp
, true, multiline
);
1047 pp_string (pp
, "}");
1052 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
1054 if (!smap
->is_empty_p ())
1057 pp_string (pp
, " {");
1058 pp_printf (pp
, "%s: ", ext_state
.get_name (i
));
1061 smap
->print (m_region_model
, true, multiline
, pp
);
1063 pp_string (pp
, "}");
1071 pp_printf (pp
, "invalid state");
1076 pp_string (pp
, "}");
1079 /* Dump a representation of this state to OUTF. */
1082 program_state::dump_to_file (const extrinsic_state
&ext_state
,
1083 bool summarize
, bool multiline
,
1087 pp_format_decoder (&pp
) = default_tree_printer
;
1089 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
1090 pp
.buffer
->stream
= outf
;
1091 dump_to_pp (ext_state
, summarize
, multiline
, &pp
);
1095 /* Dump a multiline representation of this state to stderr. */
1098 program_state::dump (const extrinsic_state
&ext_state
,
1099 bool summarize
) const
1101 dump_to_file (ext_state
, summarize
, true, stderr
);
1104 /* Return a new json::object of the form
1105 {"store" : object for store,
1106 "constraints" : object for constraint_manager,
1107 "curr_frame" : (optional) str for current frame,
1108 "checkers" : { STATE_NAME : object per sm_state_map },
1109 "valid" : true/false}. */
1112 program_state::to_json (const extrinsic_state
&ext_state
) const
1114 json::object
*state_obj
= new json::object ();
1116 state_obj
->set ("store", m_region_model
->get_store ()->to_json ());
1117 state_obj
->set ("constraints",
1118 m_region_model
->get_constraints ()->to_json ());
1119 if (m_region_model
->get_current_frame ())
1120 state_obj
->set ("curr_frame",
1121 m_region_model
->get_current_frame ()->to_json ());
1123 /* Provide m_checker_states as an object, using names as keys. */
1125 json::object
*checkers_obj
= new json::object ();
1129 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
1130 if (!smap
->is_empty_p ())
1131 checkers_obj
->set (ext_state
.get_name (i
), smap
->to_json ());
1133 state_obj
->set ("checkers", checkers_obj
);
1136 state_obj
->set ("valid", new json::literal (m_valid
));
1141 /* Update this program_state to reflect a top-level call to FUN.
1142 The params will have initial_svalues. */
1145 program_state::push_frame (const extrinsic_state
&ext_state ATTRIBUTE_UNUSED
,
1146 const function
&fun
)
1148 m_region_model
->push_frame (fun
, NULL
, NULL
);
1151 /* Get the current function of this state. */
1154 program_state::get_current_function () const
1156 return m_region_model
->get_current_function ();
1159 /* Determine if following edge SUCC from ENODE is valid within the graph EG
1160 and update this state accordingly in-place.
1162 Return true if the edge can be followed, or false otherwise.
1164 Check for relevant conditionals and switch-values for conditionals
1165 and switch statements, adding the relevant conditions to this state.
1166 Push/pop frames for interprocedural edges and update params/returned
1169 This is the "state" half of exploded_node::on_edge. */
1172 program_state::on_edge (exploded_graph
&eg
,
1173 exploded_node
*enode
,
1174 const superedge
*succ
,
1175 uncertainty_t
*uncertainty
)
1177 class my_path_context
: public path_context
1180 my_path_context (bool &terminated
) : m_terminated (terminated
) {}
1181 void bifurcate (std::unique_ptr
<custom_edge_info
>) final override
1186 void terminate_path () final override
1188 m_terminated
= true;
1191 bool terminate_path_p () const final override
1193 return m_terminated
;
1199 const program_point
&point
= enode
->get_point ();
1200 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1202 /* For conditionals and switch statements, add the
1203 relevant conditions (for the specific edge) to new_state;
1204 skip edges for which the resulting constraints
1206 This also updates frame information for call/return superedges.
1207 Adding the relevant conditions for the edge could also trigger
1208 sm-state transitions (e.g. transitions due to ptrs becoming known
1209 to be NULL or non-NULL) */
1210 bool terminated
= false;
1211 my_path_context
path_ctxt (terminated
);
1212 impl_region_model_context
ctxt (eg
, enode
,
1213 &enode
->get_state (),
1215 uncertainty
, &path_ctxt
,
1217 std::unique_ptr
<rejected_constraint
> rc
;
1218 logger
* const logger
= eg
.get_logger ();
1219 if (!m_region_model
->maybe_update_for_edge (*succ
,
1222 logger
? &rc
: nullptr))
1226 logger
->start_log_line ();
1227 logger
->log_partial ("edge to SN: %i is impossible"
1228 " due to region_model constraint: ",
1229 succ
->m_dest
->m_index
);
1230 rc
->dump_to_pp (logger
->get_printer ());
1231 logger
->end_log_line ();
1238 program_state::detect_leaks (enode
->get_state (), *this,
1239 NULL
, eg
.get_ext_state (),
1245 /* Update this program_state to reflect a call to function
1246 represented by CALL_STMT.
1247 currently used only when the call doesn't have a superedge representing
1248 the call ( like call via a function pointer ) */
1250 program_state::push_call (exploded_graph
&eg
,
1251 exploded_node
*enode
,
1252 const gcall
*call_stmt
,
1253 uncertainty_t
*uncertainty
)
1256 const program_point
&point
= enode
->get_point ();
1257 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1259 impl_region_model_context
ctxt (eg
, enode
,
1260 &enode
->get_state (),
1265 m_region_model
->update_for_gcall (call_stmt
, &ctxt
);
1268 /* Update this program_state to reflect a return from function
1269 call to which is represented by CALL_STMT.
1270 currently used only when the call doesn't have a superedge representing
1273 program_state::returning_call (exploded_graph
&eg
,
1274 exploded_node
*enode
,
1275 const gcall
*call_stmt
,
1276 uncertainty_t
*uncertainty
)
1279 const program_point
&point
= enode
->get_point ();
1280 const gimple
*last_stmt
= point
.get_supernode ()->get_last_stmt ();
1282 impl_region_model_context
ctxt (eg
, enode
,
1283 &enode
->get_state (),
1288 m_region_model
->update_for_return_gcall (call_stmt
, &ctxt
);
1291 /* Generate a simpler version of THIS, discarding state that's no longer
1293 The idea is that we're more likely to be able to consolidate
1294 multiple (point, state) into single exploded_nodes if we discard
1295 irrelevant state (e.g. at the end of functions). */
1298 program_state::prune_for_point (exploded_graph
&eg
,
1299 const program_point
&point
,
1300 exploded_node
*enode_for_diag
,
1301 uncertainty_t
*uncertainty
) const
1303 logger
* const logger
= eg
.get_logger ();
1306 function
*fun
= point
.get_function ();
1310 program_state
new_state (*this);
1312 const state_purge_map
*pm
= eg
.get_purge_map ();
1315 unsigned num_ssas_purged
= 0;
1316 unsigned num_decls_purged
= 0;
1317 auto_vec
<const decl_region
*> regs
;
1318 new_state
.m_region_model
->get_regions_for_current_frame (®s
);
1319 regs
.qsort (region::cmp_ptr_ptr
);
1321 const decl_region
*reg
;
1322 FOR_EACH_VEC_ELT (regs
, i
, reg
)
1324 const tree node
= reg
->get_decl ();
1325 if (TREE_CODE (node
) == SSA_NAME
)
1327 const tree ssa_name
= node
;
1328 const state_purge_per_ssa_name
&per_ssa
1329 = pm
->get_data_for_ssa_name (node
);
1330 if (!per_ssa
.needed_at_point_p (point
.get_function_point ()))
1332 /* Don't purge bindings of SSA names to svalues
1333 that have unpurgable sm-state, so that leaks are
1334 reported at the end of the function, rather than
1335 at the last place that such an SSA name is referred to.
1337 But do purge them for temporaries (when SSA_NAME_VAR is
1338 NULL), so that we report for cases where a leak happens when
1339 a variable is overwritten with another value, so that the leak
1340 is reported at the point of overwrite, rather than having
1341 temporaries keep the value reachable until the frame is
1344 = new_state
.m_region_model
->get_store_value (reg
, NULL
);
1345 if (!new_state
.can_purge_p (eg
.get_ext_state (), sval
)
1346 && SSA_NAME_VAR (ssa_name
))
1348 /* (currently only state maps can keep things
1351 logger
->log ("not purging binding for %qE"
1352 " (used by state map)", ssa_name
);
1356 new_state
.m_region_model
->purge_region (reg
);
1362 const tree decl
= node
;
1363 gcc_assert (TREE_CODE (node
) == VAR_DECL
1364 || TREE_CODE (node
) == PARM_DECL
1365 || TREE_CODE (node
) == RESULT_DECL
);
1366 if (const state_purge_per_decl
*per_decl
1367 = pm
->get_any_data_for_decl (decl
))
1368 if (!per_decl
->needed_at_point_p (point
.get_function_point ()))
1370 /* Don't purge bindings of decls if there are svalues
1371 that have unpurgable sm-state within the decl's cluster,
1372 so that leaks are reported at the end of the function,
1373 rather than at the last place that such a decl is
1375 if (!new_state
.can_purge_base_region_p (eg
.get_ext_state (),
1378 /* (currently only state maps can keep things
1381 logger
->log ("not purging binding for %qE"
1382 " (value in binding used by state map)",
1387 new_state
.m_region_model
->purge_region (reg
);
1393 if (num_ssas_purged
> 0 || num_decls_purged
> 0)
1397 logger
->log ("num_ssas_purged: %i", num_ssas_purged
);
1398 logger
->log ("num_decl_purged: %i", num_decls_purged
);
1400 impl_region_model_context
ctxt (eg
, enode_for_diag
,
1405 detect_leaks (*this, new_state
, NULL
, eg
.get_ext_state (), &ctxt
);
1409 new_state
.m_region_model
->canonicalize ();
1414 /* Return true if there are no unpurgeable bindings within BASE_REG. */
1417 program_state::can_purge_base_region_p (const extrinsic_state
&ext_state
,
1418 const region
*base_reg
) const
1420 binding_cluster
*cluster
1421 = m_region_model
->get_store ()->get_cluster (base_reg
);
1425 for (auto iter
: *cluster
)
1427 const svalue
*sval
= iter
.second
;
1428 if (!can_purge_p (ext_state
, sval
))
1435 /* Get a representative tree to use for describing SVAL. */
1438 program_state::get_representative_tree (const svalue
*sval
) const
1440 gcc_assert (m_region_model
);
1441 return m_region_model
->get_representative_tree (sval
);
1444 /* Attempt to merge this state with OTHER, both at POINT.
1445 Write the result to *OUT.
1446 If the states were merged successfully, return true. */
1449 program_state::can_merge_with_p (const program_state
&other
,
1450 const extrinsic_state
&ext_state
,
1451 const program_point
&point
,
1452 program_state
*out
) const
1455 gcc_assert (m_region_model
);
1457 /* Attempt to merge the sm-states. */
1460 FOR_EACH_VEC_ELT (out
->m_checker_states
, i
, smap
)
1461 if (!m_checker_states
[i
]->can_merge_with_p (*other
.m_checker_states
[i
],
1462 ext_state
.get_sm (i
),
1464 &out
->m_checker_states
[i
]))
1467 /* Attempt to merge the region_models. */
1468 if (!m_region_model
->can_merge_with_p (*other
.m_region_model
,
1470 out
->m_region_model
,
1475 out
->m_region_model
->canonicalize ();
1480 /* Assert that this object is valid. */
1483 program_state::validate (const extrinsic_state
&ext_state
) const
1485 /* Skip this in a release build. */
1490 gcc_assert (m_checker_states
.length () == ext_state
.get_num_checkers ());
1491 m_region_model
->validate ();
1495 log_set_of_svalues (logger
*logger
, const char *name
,
1496 const svalue_set
&set
)
1499 logger
->inc_indent ();
1500 auto_vec
<const svalue
*> sval_vecs (set
.elements ());
1501 for (svalue_set::iterator iter
= set
.begin ();
1502 iter
!= set
.end (); ++iter
)
1503 sval_vecs
.quick_push (*iter
);
1504 sval_vecs
.qsort (svalue::cmp_ptr_ptr
);
1507 FOR_EACH_VEC_ELT (sval_vecs
, i
, sval
)
1509 logger
->start_log_line ();
1510 pretty_printer
*pp
= logger
->get_printer ();
1511 if (!flag_dump_noaddr
)
1513 pp_pointer (pp
, sval
);
1514 pp_string (pp
, ": ");
1516 sval
->dump_to_pp (pp
, false);
1517 logger
->end_log_line ();
1519 logger
->dec_indent ();
1522 /* Compare the sets of svalues reachable from each of SRC_STATE and DEST_STATE.
1523 For all svalues that are reachable in SRC_STATE and are not live in
1524 DEST_STATE (whether explicitly reachable in DEST_STATE, or implicitly live
1525 based on the former set), call CTXT->on_svalue_leak for them.
1527 Call on_liveness_change on both the CTXT and on the DEST_STATE's
1528 constraint_manager, purging dead svalues from sm-state and from
1529 constraints, respectively.
1531 This function should be called at each fine-grained state change, not
1532 just at exploded edges. */
1535 program_state::detect_leaks (const program_state
&src_state
,
1536 const program_state
&dest_state
,
1537 const svalue
*extra_sval
,
1538 const extrinsic_state
&ext_state
,
1539 region_model_context
*ctxt
)
1541 logger
*logger
= ext_state
.get_logger ();
1543 const uncertainty_t
*uncertainty
= ctxt
->get_uncertainty ();
1546 pretty_printer
*pp
= logger
->get_printer ();
1547 logger
->start_log_line ();
1548 pp_string (pp
, "src_state: ");
1549 src_state
.dump_to_pp (ext_state
, true, false, pp
);
1550 logger
->end_log_line ();
1551 logger
->start_log_line ();
1552 pp_string (pp
, "dest_state: ");
1553 dest_state
.dump_to_pp (ext_state
, true, false, pp
);
1554 logger
->end_log_line ();
1557 logger
->start_log_line ();
1558 pp_string (pp
, "extra_sval: ");
1559 extra_sval
->dump_to_pp (pp
, true);
1560 logger
->end_log_line ();
1564 logger
->start_log_line ();
1565 pp_string (pp
, "uncertainty: ");
1566 uncertainty
->dump_to_pp (pp
, true);
1567 logger
->end_log_line ();
1571 /* Get svalues reachable from each of src_state and dest_state.
1572 Get svalues *known* to be reachable in src_state.
1573 Pass in uncertainty for dest_state so that we additionally get svalues that
1574 *might* still be reachable in dst_state. */
1575 svalue_set known_src_svalues
;
1576 src_state
.m_region_model
->get_reachable_svalues (&known_src_svalues
,
1578 svalue_set maybe_dest_svalues
;
1579 dest_state
.m_region_model
->get_reachable_svalues (&maybe_dest_svalues
,
1580 extra_sval
, uncertainty
);
1584 log_set_of_svalues (logger
, "src_state known reachable svalues:",
1586 log_set_of_svalues (logger
, "dest_state maybe reachable svalues:",
1587 maybe_dest_svalues
);
1590 auto_vec
<const svalue
*> dead_svals (known_src_svalues
.elements ());
1591 for (svalue_set::iterator iter
= known_src_svalues
.begin ();
1592 iter
!= known_src_svalues
.end (); ++iter
)
1594 const svalue
*sval
= (*iter
);
1595 /* For each sval reachable from SRC_STATE, determine if it is
1596 live in DEST_STATE: either explicitly reachable, implicitly
1597 live based on the set of explicitly reachable svalues,
1598 or possibly reachable as recorded in uncertainty.
1599 Record those that have ceased to be live i.e. were known
1600 to be live, and are now not known to be even possibly-live. */
1601 if (!sval
->live_p (&maybe_dest_svalues
, dest_state
.m_region_model
))
1602 dead_svals
.quick_push (sval
);
1605 /* Call CTXT->on_svalue_leak on all svals in SRC_STATE that have ceased
1606 to be live, sorting them first to ensure deterministic behavior. */
1607 dead_svals
.qsort (svalue::cmp_ptr_ptr
);
1610 FOR_EACH_VEC_ELT (dead_svals
, i
, sval
)
1611 ctxt
->on_svalue_leak (sval
);
1613 /* Purge dead svals from sm-state. */
1614 ctxt
->on_liveness_change (maybe_dest_svalues
,
1615 dest_state
.m_region_model
);
1617 /* Purge dead svals from constraints. */
1618 dest_state
.m_region_model
->get_constraints ()->on_liveness_change
1619 (maybe_dest_svalues
, dest_state
.m_region_model
);
1621 /* Purge dead heap-allocated regions from dynamic extents. */
1622 for (const svalue
*sval
: dead_svals
)
1623 if (const region
*reg
= sval
->maybe_get_region ())
1624 if (reg
->get_kind () == RK_HEAP_ALLOCATED
)
1625 dest_state
.m_region_model
->unset_dynamic_extents (reg
);
1628 /* Attempt to to use R to replay SUMMARY into this object.
1629 Return true if it is possible. */
1632 program_state::replay_call_summary (call_summary_replay
&r
,
1633 const program_state
&summary
)
1635 if (!m_region_model
->replay_call_summary (r
, *summary
.m_region_model
))
1638 for (unsigned sm_idx
= 0; sm_idx
< m_checker_states
.length (); sm_idx
++)
1640 const sm_state_map
*summary_sm_map
= summary
.m_checker_states
[sm_idx
];
1641 m_checker_states
[sm_idx
]->replay_call_summary (r
, *summary_sm_map
);
1644 if (!summary
.m_valid
)
1650 /* Handle calls to "__analyzer_dump_state". */
1653 program_state::impl_call_analyzer_dump_state (const gcall
*call
,
1654 const extrinsic_state
&ext_state
,
1655 region_model_context
*ctxt
)
1657 call_details
cd (call
, m_region_model
, ctxt
);
1658 const char *sm_name
= cd
.get_arg_string_literal (0);
1661 error_at (call
->location
, "cannot determine state machine");
1665 if (!ext_state
.get_sm_idx_by_name (sm_name
, &sm_idx
))
1667 error_at (call
->location
, "unrecognized state machine %qs", sm_name
);
1670 const sm_state_map
*smap
= m_checker_states
[sm_idx
];
1672 const svalue
*sval
= cd
.get_arg_svalue (1);
1674 /* Strip off cast to int (due to variadic args). */
1675 if (const svalue
*cast
= sval
->maybe_undo_cast ())
1678 state_machine::state_t state
= smap
->get_state (sval
, ext_state
);
1679 warning_at (call
->location
, 0, "state: %qs", state
->get_name ());
1684 namespace selftest
{
1686 /* Tests for sm_state_map. */
1689 test_sm_state_map ()
1691 tree x
= build_global_decl ("x", integer_type_node
);
1692 tree y
= build_global_decl ("y", integer_type_node
);
1693 tree z
= build_global_decl ("z", integer_type_node
);
1695 state_machine
*sm
= make_malloc_state_machine (NULL
);
1696 auto_delete_vec
<state_machine
> checkers
;
1697 checkers
.safe_push (sm
);
1699 extrinsic_state
ext_state (checkers
, &eng
);
1700 state_machine::state_t start
= sm
->get_start_state ();
1702 /* Test setting states on svalue_id instances directly. */
1704 const state_machine::state
test_state_42 ("test state 42", 42);
1705 const state_machine::state_t TEST_STATE_42
= &test_state_42
;
1706 region_model_manager mgr
;
1707 region_model
model (&mgr
);
1708 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1709 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1710 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1712 sm_state_map
map (*sm
);
1713 ASSERT_TRUE (map
.is_empty_p ());
1714 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1716 map
.impl_set_state (x_sval
, TEST_STATE_42
, z_sval
, ext_state
);
1717 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), TEST_STATE_42
);
1718 ASSERT_EQ (map
.get_origin (x_sval
, ext_state
), z_sval
);
1719 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1720 ASSERT_FALSE (map
.is_empty_p ());
1722 map
.impl_set_state (y_sval
, 0, z_sval
, ext_state
);
1723 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1725 map
.impl_set_state (x_sval
, 0, z_sval
, ext_state
);
1726 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1727 ASSERT_TRUE (map
.is_empty_p ());
1730 const state_machine::state
test_state_5 ("test state 5", 5);
1731 const state_machine::state_t TEST_STATE_5
= &test_state_5
;
1733 /* Test setting states via equivalence classes. */
1735 region_model_manager mgr
;
1736 region_model
model (&mgr
);
1737 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1738 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1739 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1741 sm_state_map
map (*sm
);
1742 ASSERT_TRUE (map
.is_empty_p ());
1743 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), start
);
1744 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), start
);
1746 model
.add_constraint (x
, EQ_EXPR
, y
, NULL
);
1748 /* Setting x to a state should also update y, as they
1749 are in the same equivalence class. */
1750 map
.set_state (&model
, x_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1751 ASSERT_EQ (map
.get_state (x_sval
, ext_state
), TEST_STATE_5
);
1752 ASSERT_EQ (map
.get_state (y_sval
, ext_state
), TEST_STATE_5
);
1753 ASSERT_EQ (map
.get_origin (x_sval
, ext_state
), z_sval
);
1754 ASSERT_EQ (map
.get_origin (y_sval
, ext_state
), z_sval
);
1757 /* Test equality and hashing. */
1759 region_model_manager mgr
;
1760 region_model
model (&mgr
);
1761 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1762 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1764 sm_state_map
map0 (*sm
);
1765 sm_state_map
map1 (*sm
);
1766 sm_state_map
map2 (*sm
);
1768 ASSERT_EQ (map0
.hash (), map1
.hash ());
1769 ASSERT_EQ (map0
, map1
);
1771 map1
.impl_set_state (y_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1772 ASSERT_NE (map0
.hash (), map1
.hash ());
1773 ASSERT_NE (map0
, map1
);
1775 /* Make the same change to map2. */
1776 map2
.impl_set_state (y_sval
, TEST_STATE_5
, z_sval
, ext_state
);
1777 ASSERT_EQ (map1
.hash (), map2
.hash ());
1778 ASSERT_EQ (map1
, map2
);
1781 /* Equality and hashing shouldn't depend on ordering. */
1783 const state_machine::state
test_state_2 ("test state 2", 2);
1784 const state_machine::state_t TEST_STATE_2
= &test_state_2
;
1785 const state_machine::state
test_state_3 ("test state 3", 3);
1786 const state_machine::state_t TEST_STATE_3
= &test_state_3
;
1787 sm_state_map
map0 (*sm
);
1788 sm_state_map
map1 (*sm
);
1789 sm_state_map
map2 (*sm
);
1791 ASSERT_EQ (map0
.hash (), map1
.hash ());
1792 ASSERT_EQ (map0
, map1
);
1794 region_model_manager mgr
;
1795 region_model
model (&mgr
);
1796 const svalue
*x_sval
= model
.get_rvalue (x
, NULL
);
1797 const svalue
*y_sval
= model
.get_rvalue (y
, NULL
);
1798 const svalue
*z_sval
= model
.get_rvalue (z
, NULL
);
1800 map1
.impl_set_state (x_sval
, TEST_STATE_2
, NULL
, ext_state
);
1801 map1
.impl_set_state (y_sval
, TEST_STATE_3
, NULL
, ext_state
);
1802 map1
.impl_set_state (z_sval
, TEST_STATE_2
, NULL
, ext_state
);
1804 map2
.impl_set_state (z_sval
, TEST_STATE_2
, NULL
, ext_state
);
1805 map2
.impl_set_state (y_sval
, TEST_STATE_3
, NULL
, ext_state
);
1806 map2
.impl_set_state (x_sval
, TEST_STATE_2
, NULL
, ext_state
);
1808 ASSERT_EQ (map1
.hash (), map2
.hash ());
1809 ASSERT_EQ (map1
, map2
);
1812 // TODO: coverage for purging
1815 /* Check program_state works as expected. */
1818 test_program_state_1 ()
1820 /* Create a program_state for a global ptr "p" that has
1821 malloc sm-state, pointing to a region on the heap. */
1822 tree p
= build_global_decl ("p", ptr_type_node
);
1824 state_machine
*sm
= make_malloc_state_machine (NULL
);
1825 const state_machine::state_t UNCHECKED_STATE
1826 = sm
->get_state_by_name ("unchecked");
1827 auto_delete_vec
<state_machine
> checkers
;
1828 checkers
.safe_push (sm
);
1831 extrinsic_state
ext_state (checkers
, &eng
);
1832 region_model_manager
*mgr
= eng
.get_model_manager ();
1833 program_state
s (ext_state
);
1834 region_model
*model
= s
.m_region_model
;
1835 const svalue
*size_in_bytes
1836 = mgr
->get_or_create_unknown_svalue (size_type_node
);
1837 const region
*new_reg
1838 = model
->get_or_create_region_for_heap_alloc (size_in_bytes
, NULL
);
1839 const svalue
*ptr_sval
= mgr
->get_ptr_svalue (ptr_type_node
, new_reg
);
1840 model
->set_value (model
->get_lvalue (p
, NULL
),
1842 sm_state_map
*smap
= s
.m_checker_states
[0];
1844 smap
->impl_set_state (ptr_sval
, UNCHECKED_STATE
, NULL
, ext_state
);
1845 ASSERT_EQ (smap
->get_state (ptr_sval
, ext_state
), UNCHECKED_STATE
);
1848 /* Check that program_state works for string literals. */
1851 test_program_state_2 ()
1853 /* Create a program_state for a global ptr "p" that points to
1854 a string constant. */
1855 tree p
= build_global_decl ("p", ptr_type_node
);
1857 tree string_cst_ptr
= build_string_literal (4, "foo");
1859 auto_delete_vec
<state_machine
> checkers
;
1861 extrinsic_state
ext_state (checkers
, &eng
);
1863 program_state
s (ext_state
);
1864 region_model
*model
= s
.m_region_model
;
1865 const region
*p_reg
= model
->get_lvalue (p
, NULL
);
1866 const svalue
*str_sval
= model
->get_rvalue (string_cst_ptr
, NULL
);
1867 model
->set_value (p_reg
, str_sval
, NULL
);
1870 /* Verify that program_states with identical sm-state can be merged,
1871 and that the merged program_state preserves the sm-state. */
1874 test_program_state_merging ()
1876 /* Create a program_state for a global ptr "p" that has
1877 malloc sm-state, pointing to a region on the heap. */
1878 tree p
= build_global_decl ("p", ptr_type_node
);
1881 region_model_manager
*mgr
= eng
.get_model_manager ();
1882 program_point
point (program_point::origin (*mgr
));
1883 auto_delete_vec
<state_machine
> checkers
;
1884 checkers
.safe_push (make_malloc_state_machine (NULL
));
1885 extrinsic_state
ext_state (checkers
, &eng
);
1887 program_state
s0 (ext_state
);
1888 uncertainty_t uncertainty
;
1889 impl_region_model_context
ctxt (&s0
, ext_state
, &uncertainty
);
1891 region_model
*model0
= s0
.m_region_model
;
1892 const svalue
*size_in_bytes
1893 = mgr
->get_or_create_unknown_svalue (size_type_node
);
1894 const region
*new_reg
1895 = model0
->get_or_create_region_for_heap_alloc (size_in_bytes
, NULL
);
1896 const svalue
*ptr_sval
= mgr
->get_ptr_svalue (ptr_type_node
, new_reg
);
1897 model0
->set_value (model0
->get_lvalue (p
, &ctxt
),
1899 sm_state_map
*smap
= s0
.m_checker_states
[0];
1900 const state_machine::state
test_state ("test state", 0);
1901 const state_machine::state_t TEST_STATE
= &test_state
;
1902 smap
->impl_set_state (ptr_sval
, TEST_STATE
, NULL
, ext_state
);
1903 ASSERT_EQ (smap
->get_state (ptr_sval
, ext_state
), TEST_STATE
);
1905 model0
->canonicalize ();
1907 /* Verify that canonicalization preserves sm-state. */
1908 ASSERT_EQ (smap
->get_state (model0
->get_rvalue (p
, NULL
), ext_state
),
1911 /* Make a copy of the program_state. */
1912 program_state
s1 (s0
);
1915 /* We have two identical states with "p" pointing to a heap region
1916 with the given sm-state.
1917 They ought to be mergeable, preserving the sm-state. */
1918 program_state
merged (ext_state
);
1919 ASSERT_TRUE (s0
.can_merge_with_p (s1
, ext_state
, point
, &merged
));
1920 merged
.validate (ext_state
);
1922 /* Verify that the merged state has the sm-state for "p". */
1923 region_model
*merged_model
= merged
.m_region_model
;
1924 sm_state_map
*merged_smap
= merged
.m_checker_states
[0];
1925 ASSERT_EQ (merged_smap
->get_state (merged_model
->get_rvalue (p
, NULL
),
1929 /* Try canonicalizing. */
1930 merged
.m_region_model
->canonicalize ();
1931 merged
.validate (ext_state
);
1933 /* Verify that the merged state still has the sm-state for "p". */
1934 ASSERT_EQ (merged_smap
->get_state (merged_model
->get_rvalue (p
, NULL
),
1938 /* After canonicalization, we ought to have equality with the inputs. */
1939 ASSERT_EQ (s0
, merged
);
1942 /* Verify that program_states with different global-state in an sm-state
1946 test_program_state_merging_2 ()
1949 region_model_manager
*mgr
= eng
.get_model_manager ();
1950 program_point
point (program_point::origin (*mgr
));
1951 auto_delete_vec
<state_machine
> checkers
;
1952 checkers
.safe_push (make_signal_state_machine (NULL
));
1953 extrinsic_state
ext_state (checkers
, &eng
);
1955 const state_machine::state
test_state_0 ("test state 0", 0);
1956 const state_machine::state
test_state_1 ("test state 1", 1);
1957 const state_machine::state_t TEST_STATE_0
= &test_state_0
;
1958 const state_machine::state_t TEST_STATE_1
= &test_state_1
;
1960 program_state
s0 (ext_state
);
1962 sm_state_map
*smap0
= s0
.m_checker_states
[0];
1963 smap0
->set_global_state (TEST_STATE_0
);
1964 ASSERT_EQ (smap0
->get_global_state (), TEST_STATE_0
);
1967 program_state
s1 (ext_state
);
1969 sm_state_map
*smap1
= s1
.m_checker_states
[0];
1970 smap1
->set_global_state (TEST_STATE_1
);
1971 ASSERT_EQ (smap1
->get_global_state (), TEST_STATE_1
);
1976 /* They ought to not be mergeable. */
1977 program_state
merged (ext_state
);
1978 ASSERT_FALSE (s0
.can_merge_with_p (s1
, ext_state
, point
, &merged
));
1981 /* Run all of the selftests within this file. */
1984 analyzer_program_state_cc_tests ()
1986 test_sm_state_map ();
1987 test_program_state_1 ();
1988 test_program_state_2 ();
1989 test_program_state_merging ();
1990 test_program_state_merging_2 ();
1993 } // namespace selftest
1995 #endif /* CHECKING_P */
1999 #endif /* #if ENABLE_ANALYZER */