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>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#define INCLUDE_MEMORY
23#include "system.h"
24#include "coretypes.h"
25#include "tree.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"
31#include "sbitmap.h"
32#include "bitmap.h"
33#include "ordered-hash-map.h"
34#include "selftest.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"
44#include "cfg.h"
45#include "basic-block.h"
46#include "gimple.h"
47#include "gimple-iterator.h"
48#include "cgraph.h"
49#include "digraph.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"
56
57#if ENABLE_ANALYZER
58
59namespace ana {
60
61/* class extrinsic_state. */
62
63/* Dump a multiline representation of this state to PP. */
64
65void
66extrinsic_state::dump_to_pp (pretty_printer *pp) const
67{
68 pp_printf (pp, "extrinsic_state: %i checker(s)\n", get_num_checkers ());
69 unsigned i;
70 state_machine *checker;
71 FOR_EACH_VEC_ELT (m_checkers, i, checker)
72 {
73 pp_printf (pp, "m_checkers[%i]: %qs\n", i, checker->get_name ());
74 checker->dump_to_pp (pp);
75 }
76}
77
78/* Dump a multiline representation of this state to OUTF. */
79
80void
81extrinsic_state::dump_to_file (FILE *outf) const
82{
83 pretty_printer pp;
84 if (outf == stderr)
85 pp_show_color (&pp) = pp_show_color (global_dc->printer);
86 pp.buffer->stream = outf;
87 dump_to_pp (pp: &pp);
88 pp_flush (&pp);
89}
90
91/* Dump a multiline representation of this state to stderr. */
92
93DEBUG_FUNCTION void
94extrinsic_state::dump () const
95{
96 dump_to_file (stderr);
97}
98
99/* Return a new json::object of the form
100 {"checkers" : array of objects, one for each state_machine}. */
101
102json::object *
103extrinsic_state::to_json () const
104{
105 json::object *ext_state_obj = new json::object ();
106
107 {
108 json::array *checkers_arr = new json::array ();
109 unsigned i;
110 state_machine *sm;
111 FOR_EACH_VEC_ELT (m_checkers, i, sm)
112 checkers_arr->append (v: sm->to_json ());
113 ext_state_obj->set (key: "checkers", v: checkers_arr);
114 }
115
116 return ext_state_obj;
117}
118
119/* Get the region_model_manager for this extrinsic_state. */
120
121region_model_manager *
122extrinsic_state::get_model_manager () const
123{
124 if (m_engine)
125 return m_engine->get_model_manager ();
126 else
127 return NULL; /* for selftests. */
128}
129
130/* Try to find a state machine named NAME.
131 If found, return true and write its index to *OUT.
132 Otherwise return false. */
133
134bool
135extrinsic_state::get_sm_idx_by_name (const char *name, unsigned *out) const
136{
137 unsigned i;
138 state_machine *sm;
139 FOR_EACH_VEC_ELT (m_checkers, i, sm)
140 if (0 == strcmp (s1: name, s2: sm->get_name ()))
141 {
142 /* Found NAME. */
143 *out = i;
144 return true;
145 }
146
147 /* NAME not found. */
148 return false;
149}
150
151/* struct sm_state_map::entry_t. */
152
153int
154sm_state_map::entry_t::cmp (const entry_t &entry_a, const entry_t &entry_b)
155{
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 ()))
160 return cmp_state;
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)
164 return 1;
165 if (entry_b.m_origin)
166 return -1;
167 return 0;
168}
169
170/* class sm_state_map. */
171
172/* sm_state_map's ctor. */
173
174sm_state_map::sm_state_map (const state_machine &sm)
175: m_sm (sm), m_map (), m_global_state (sm.get_start_state ())
176{
177}
178
179/* Clone the sm_state_map. */
180
181sm_state_map *
182sm_state_map::clone () const
183{
184 return new sm_state_map (*this);
185}
186
187/* Print this sm_state_map to PP.
188 If MODEL is non-NULL, print representative tree values where
189 available. */
190
191void
192sm_state_map::print (const region_model *model,
193 bool simple, bool multiline,
194 pretty_printer *pp) const
195{
196 bool first = true;
197 if (!multiline)
198 pp_string (pp, "{");
199 if (m_global_state != m_sm.get_start_state ())
200 {
201 if (multiline)
202 pp_string (pp, " ");
203 pp_string (pp, "global: ");
204 m_global_state->dump_to_pp (pp);
205 if (multiline)
206 pp_newline (pp);
207 first = false;
208 }
209 auto_vec <const svalue *> keys (m_map.elements ());
210 for (map_t::iterator iter = m_map.begin ();
211 iter != m_map.end ();
212 ++iter)
213 keys.quick_push (obj: (*iter).first);
214 keys.qsort (svalue::cmp_ptr_ptr);
215 unsigned i;
216 const svalue *sval;
217 FOR_EACH_VEC_ELT (keys, i, sval)
218 {
219 if (multiline)
220 pp_string (pp, " ");
221 else if (!first)
222 pp_string (pp, ", ");
223 first = false;
224 if (!flag_dump_noaddr)
225 {
226 pp_pointer (pp, sval);
227 pp_string (pp, ": ");
228 }
229 sval->dump_to_pp (pp, simple);
230
231 entry_t e = *const_cast <map_t &> (m_map).get (k: sval);
232 pp_string (pp, ": ");
233 e.m_state->dump_to_pp (pp);
234 if (model)
235 if (tree rep = model->get_representative_tree (sval))
236 {
237 pp_string (pp, " (");
238 dump_quoted_tree (pp, t: rep);
239 pp_character (pp, ')');
240 }
241 if (e.m_origin)
242 {
243 pp_string (pp, " (origin: ");
244 if (!flag_dump_noaddr)
245 {
246 pp_pointer (pp, e.m_origin);
247 pp_string (pp, ": ");
248 }
249 e.m_origin->dump_to_pp (pp, simple);
250 if (model)
251 if (tree rep = model->get_representative_tree (sval: e.m_origin))
252 {
253 pp_string (pp, " (");
254 dump_quoted_tree (pp, t: rep);
255 pp_character (pp, ')');
256 }
257 pp_string (pp, ")");
258 }
259 if (multiline)
260 pp_newline (pp);
261 }
262 if (!multiline)
263 pp_string (pp, "}");
264}
265
266/* Dump this object to stderr. */
267
268DEBUG_FUNCTION void
269sm_state_map::dump (bool simple) const
270{
271 pretty_printer pp;
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, multiline: true, pp: &pp);
276 pp_newline (&pp);
277 pp_flush (&pp);
278}
279
280/* Return a new json::object of the form
281 {"global" : (optional) value for global state,
282 SVAL_DESC : value for state}. */
283
284json::object *
285sm_state_map::to_json () const
286{
287 json::object *map_obj = new json::object ();
288
289 if (m_global_state != m_sm.get_start_state ())
290 map_obj->set (key: "global", v: m_global_state->to_json ());
291 for (map_t::iterator iter = m_map.begin ();
292 iter != m_map.end ();
293 ++iter)
294 {
295 const svalue *sval = (*iter).first;
296 entry_t e = (*iter).second;
297
298 label_text sval_desc = sval->get_desc ();
299 map_obj->set (key: sval_desc.get (), v: e.m_state->to_json ());
300
301 /* This doesn't yet JSONify e.m_origin. */
302 }
303 return map_obj;
304}
305
306/* Return true if no states have been set within this map
307 (all expressions are for the start state). */
308
309bool
310sm_state_map::is_empty_p () const
311{
312 return m_map.elements () == 0 && m_global_state == m_sm.get_start_state ();
313}
314
315/* Generate a hash value for this sm_state_map. */
316
317hashval_t
318sm_state_map::hash () const
319{
320 hashval_t result = 0;
321
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. */
324
325 for (map_t::iterator iter = m_map.begin ();
326 iter != m_map.end ();
327 ++iter)
328 {
329 inchash::hash hstate;
330 hstate.add_ptr (ptr: (*iter).first);
331 entry_t e = (*iter).second;
332 hstate.add_int (v: e.m_state->get_id ());
333 hstate.add_ptr (ptr: e.m_origin);
334 result ^= hstate.end ();
335 }
336 result ^= m_global_state->get_id ();
337
338 return result;
339}
340
341/* Equality operator for sm_state_map. */
342
343bool
344sm_state_map::operator== (const sm_state_map &other) const
345{
346 if (m_global_state != other.m_global_state)
347 return false;
348
349 if (m_map.elements () != other.m_map.elements ())
350 return false;
351
352 for (map_t::iterator iter = m_map.begin ();
353 iter != m_map.end ();
354 ++iter)
355 {
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 (k: sval);
359 if (other_slot == NULL)
360 return false;
361 if (e != *other_slot)
362 return false;
363 }
364
365 gcc_checking_assert (hash () == other.hash ());
366
367 return true;
368}
369
370/* Get the state of SVAL within this object.
371 States default to the start state. */
372
373state_machine::state_t
374sm_state_map::get_state (const svalue *sval,
375 const extrinsic_state &ext_state) const
376{
377 gcc_assert (sval);
378
379 sval = canonicalize_svalue (sval, ext_state);
380
381 if (entry_t *slot
382 = const_cast <map_t &> (m_map).get (k: sval))
383 return slot->m_state;
384
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
389 INIT_VAL(foo). */
390 if (m_sm.inherited_state_p ())
391 if (region_model_manager *mgr = ext_state.get_model_manager ())
392 {
393 if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
394 {
395 const region *reg = init_sval->get_region ();
396 /* Try recursing upwards (up to the base region for the
397 cluster). */
398 if (!reg->base_region_p ())
399 if (const region *parent_reg = reg->get_parent_region ())
400 {
401 const svalue *parent_init_sval
402 = mgr->get_or_create_initial_value (reg: parent_reg);
403 state_machine::state_t parent_state
404 = get_state (sval: parent_init_sval, ext_state);
405 if (parent_state)
406 return parent_state;
407 }
408 }
409 else if (const sub_svalue *sub_sval = sval->dyn_cast_sub_svalue ())
410 {
411 const svalue *parent_sval = sub_sval->get_parent ();
412 if (state_machine::state_t parent_state
413 = get_state (sval: parent_sval, ext_state))
414 return parent_state;
415 }
416 }
417
418 if (state_machine::state_t state
419 = m_sm.alt_get_inherited_state (*this, sval, ext_state))
420 return state;
421
422 return m_sm.get_default_state (sval);
423}
424
425/* Get the "origin" svalue for any state of SVAL. */
426
427const svalue *
428sm_state_map::get_origin (const svalue *sval,
429 const extrinsic_state &ext_state) const
430{
431 gcc_assert (sval);
432
433 sval = canonicalize_svalue (sval, ext_state);
434
435 entry_t *slot
436 = const_cast <map_t &> (m_map).get (k: sval);
437 if (slot)
438 return slot->m_origin;
439 else
440 return NULL;
441}
442
443/* Set the state of SID within MODEL to STATE, recording that
444 the state came from ORIGIN. */
445
446void
447sm_state_map::set_state (region_model *model,
448 const svalue *sval,
449 state_machine::state_t state,
450 const svalue *origin,
451 const extrinsic_state &ext_state)
452{
453 if (model == NULL)
454 return;
455
456 /* Reject attempts to set state on UNKNOWN/POISONED. */
457 if (!sval->can_have_associated_state_p ())
458 return;
459
460 equiv_class &ec = model->get_constraints ()->get_equiv_class (sval);
461 if (!set_state (ec, state, origin, ext_state))
462 return;
463}
464
465/* Set the state of EC to STATE, recording that the state came from
466 ORIGIN.
467 Return true if any states of svalue_ids within EC changed. */
468
469bool
470sm_state_map::set_state (const equiv_class &ec,
471 state_machine::state_t state,
472 const svalue *origin,
473 const extrinsic_state &ext_state)
474{
475 bool any_changed = false;
476 for (const svalue *sval : ec.m_vars)
477 any_changed |= impl_set_state (sval, state, origin, ext_state);
478 return any_changed;
479}
480
481/* Set state of SVAL to STATE, bypassing equivalence classes.
482 Return true if the state changed. */
483
484bool
485sm_state_map::impl_set_state (const svalue *sval,
486 state_machine::state_t state,
487 const svalue *origin,
488 const extrinsic_state &ext_state)
489{
490 sval = canonicalize_svalue (sval, ext_state);
491
492 if (get_state (sval, ext_state) == state)
493 return false;
494
495 gcc_assert (sval->can_have_associated_state_p ());
496
497 if (m_sm.inherited_state_p ())
498 {
499 if (const compound_svalue *compound_sval
500 = sval->dyn_cast_compound_svalue ())
501 for (auto iter : *compound_sval)
502 {
503 const svalue *inner_sval = iter.second;
504 if (inner_sval->can_have_associated_state_p ())
505 impl_set_state (sval: inner_sval, state, origin, ext_state);
506 }
507 }
508
509 /* Special-case state 0 as the default value. */
510 if (state == 0)
511 {
512 if (m_map.get (k: sval))
513 m_map.remove (k: sval);
514 return true;
515 }
516 gcc_assert (sval);
517 m_map.put (k: sval, v: entry_t (state, origin));
518 return true;
519}
520
521/* Clear any state for SVAL from this state map. */
522
523void
524sm_state_map::clear_any_state (const svalue *sval)
525{
526 m_map.remove (k: sval);
527}
528
529/* Clear all per-svalue state within this state map. */
530
531void
532sm_state_map::clear_all_per_svalue_state ()
533{
534 m_map.empty ();
535}
536
537/* Set the "global" state within this state map to STATE. */
538
539void
540sm_state_map::set_global_state (state_machine::state_t state)
541{
542 m_global_state = state;
543}
544
545/* Get the "global" state within this state map. */
546
547state_machine::state_t
548sm_state_map::get_global_state () const
549{
550 return m_global_state;
551}
552
553/* Purge any state for SVAL.
554 If !SM::can_purge_p, then report the state as leaking,
555 using CTXT. */
556
557void
558sm_state_map::on_svalue_leak (const svalue *sval,
559 impl_region_model_context *ctxt)
560{
561 if (state_machine::state_t state = get_state (sval, ext_state: ctxt->m_ext_state))
562 {
563 if (m_sm.can_purge_p (s: state))
564 m_map.remove (k: sval);
565 else
566 ctxt->on_state_leak (sm: m_sm, sval, state);
567 }
568}
569
570/* Purge any state for svalues that aren't live with respect to LIVE_SVALUES
571 and MODEL. */
572
573void
574sm_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)
578{
579 svalue_set svals_to_unset;
580 uncertainty_t *uncertainty = ctxt->get_uncertainty ();
581
582 auto_vec<const svalue *> leaked_svals (m_map.elements ());
583 for (map_t::iterator iter = m_map.begin ();
584 iter != m_map.end ();
585 ++iter)
586 {
587 const svalue *iter_sval = (*iter).first;
588 if (!iter_sval->live_p (live_svalues: &live_svalues, model))
589 {
590 svals_to_unset.add (k: iter_sval);
591 entry_t e = (*iter).second;
592 if (!m_sm.can_purge_p (s: e.m_state))
593 leaked_svals.quick_push (obj: iter_sval);
594 }
595 if (uncertainty)
596 if (uncertainty->unknown_sm_state_p (sval: iter_sval))
597 svals_to_unset.add (k: iter_sval);
598 }
599
600 leaked_svals.qsort (svalue::cmp_ptr_ptr);
601
602 unsigned i;
603 const svalue *sval;
604 FOR_EACH_VEC_ELT (leaked_svals, i, sval)
605 {
606 entry_t e = *m_map.get (k: sval);
607 ctxt->on_state_leak (sm: m_sm, sval, state: e.m_state);
608 }
609
610 sm_state_map old_sm_map = *this;
611
612 for (svalue_set::iterator iter = svals_to_unset.begin ();
613 iter != svals_to_unset.end (); ++iter)
614 m_map.remove (k: *iter);
615
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.
619
620 Consider e.g.:
621
622 make_tainted(foo);
623 if (foo.field > 128)
624 return;
625 arr[foo.field].f1 = v1;
626
627 where the last line is:
628
629 (A): _t1 = foo.field;
630 (B): _t2 = _t1 * sizeof(arr[0]);
631 (C): [arr + _t2].f1 = val;
632
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.
637
638 Given that _t2's value's state comes from _t1's value's state,
639 we need to preserve that information.
640
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.
644
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).
648
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
652 value. */
653 if (m_sm.has_alt_get_inherited_state_p ())
654 {
655 auto_vec<const svalue *> svalues_needing_state;
656 for (auto unset_sval : svals_to_unset)
657 {
658 const state_machine::state_t old_state
659 = old_sm_map.get_state (sval: unset_sval, ext_state);
660 const state_machine::state_t new_state
661 = get_state (sval: unset_sval, ext_state);
662 if (new_state != old_state)
663 svalues_needing_state.safe_push (obj: unset_sval);
664 }
665 for (auto sval : svalues_needing_state)
666 {
667 const state_machine::state_t old_state
668 = old_sm_map.get_state (sval, ext_state);
669 impl_set_state (sval, state: old_state, origin: nullptr, ext_state);
670 }
671 }
672}
673
674/* Purge state from SVAL (in response to a call to an unknown function). */
675
676void
677sm_state_map::on_unknown_change (const svalue *sval,
678 bool is_mutable,
679 const extrinsic_state &ext_state)
680{
681 svalue_set svals_to_unset;
682
683 for (map_t::iterator iter = m_map.begin ();
684 iter != m_map.end ();
685 ++iter)
686 {
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 (s: e.m_state, is_mutable))
693 continue;
694 if (key == sval)
695 svals_to_unset.add (k: 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 ())
700 {
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 (k: key);
705 }
706 }
707
708 for (svalue_set::iterator iter = svals_to_unset.begin ();
709 iter != svals_to_unset.end (); ++iter)
710 impl_set_state (sval: *iter, state: (state_machine::state_t)0, NULL, ext_state);
711}
712
713/* Purge state for things involving SVAL.
714 For use when SVAL changes meaning, at the def_stmt on an SSA_NAME. */
715
716void
717sm_state_map::purge_state_involving (const svalue *sval,
718 const extrinsic_state &ext_state)
719{
720 /* Currently svalue::involves_p requires this. */
721 if (!(sval->get_kind () == SK_INITIAL
722 || sval->get_kind () == SK_CONJURED))
723 return;
724
725 svalue_set svals_to_unset;
726
727 for (map_t::iterator iter = m_map.begin ();
728 iter != m_map.end ();
729 ++iter)
730 {
731 const svalue *key = (*iter).first;
732 entry_t e = (*iter).second;
733 if (!m_sm.can_purge_p (s: e.m_state))
734 continue;
735 if (key->involves_p (other: sval))
736 svals_to_unset.add (k: key);
737 }
738
739 for (svalue_set::iterator iter = svals_to_unset.begin ();
740 iter != svals_to_unset.end (); ++iter)
741 impl_set_state (sval: *iter, state: (state_machine::state_t)0, NULL, ext_state);
742}
743
744/* Comparator for imposing an order on sm_state_map instances. */
745
746int
747sm_state_map::cmp (const sm_state_map &smap_a, const sm_state_map &smap_b)
748{
749 if (int cmp_count = smap_a.elements () - smap_b.elements ())
750 return cmp_count;
751
752 auto_vec <const svalue *> keys_a (smap_a.elements ());
753 for (map_t::iterator iter = smap_a.begin ();
754 iter != smap_a.end ();
755 ++iter)
756 keys_a.quick_push (obj: (*iter).first);
757 keys_a.qsort (svalue::cmp_ptr_ptr);
758
759 auto_vec <const svalue *> keys_b (smap_b.elements ());
760 for (map_t::iterator iter = smap_b.begin ();
761 iter != smap_b.end ();
762 ++iter)
763 keys_b.quick_push (obj: (*iter).first);
764 keys_b.qsort (svalue::cmp_ptr_ptr);
765
766 unsigned i;
767 const svalue *sval_a;
768 FOR_EACH_VEC_ELT (keys_a, i, sval_a)
769 {
770 const svalue *sval_b = keys_b[i];
771 if (int cmp_sval = svalue::cmp_ptr (sval_a, sval_b))
772 return cmp_sval;
773 const entry_t *e_a = const_cast <map_t &> (smap_a.m_map).get (k: sval_a);
774 const entry_t *e_b = const_cast <map_t &> (smap_b.m_map).get (k: sval_b);
775 if (int cmp_entry = entry_t::cmp (entry_a: *e_a, entry_b: *e_b))
776 return cmp_entry;
777 }
778
779 return 0;
780}
781
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. */
785
786const svalue *
787sm_state_map::canonicalize_svalue (const svalue *sval,
788 const extrinsic_state &ext_state)
789{
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 ())
793 if (zerop (cst))
794 return mgr->get_or_create_constant_svalue (null_pointer_node);
795
796 return sval;
797}
798
799/* Attempt to merge this state map with OTHER, writing the result
800 into *OUT.
801 Return true if the merger was possible, false otherwise.
802
803 Normally, only identical state maps can be merged, so that
804 differences between state maps lead to different enodes
805
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. */
809
810bool
811sm_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
815{
816 /* If identical, then they merge trivially, with a copy. */
817 if (*this == other)
818 {
819 delete *out;
820 *out = clone ();
821 return true;
822 }
823
824 delete *out;
825 *out = new sm_state_map (sm);
826
827 /* Otherwise, attempt to merge element by element. */
828
829 /* Try to merge global state. */
830 if (state_machine::state_t merged_global_state
831 = sm.maybe_get_merged_state (state_a: get_global_state (),
832 state_b: other.get_global_state ()))
833 (*out)->set_global_state (merged_global_state);
834 else
835 return false;
836
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 (k: kv.first);
843 for (auto kv : other)
844 svals.add (k: kv.first);
845 for (auto sval : svals)
846 {
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 (state_a: this_state, state_b: other_state))
851 (*out)->impl_set_state (sval, state: merged_state, NULL, ext_state);
852 else
853 return false;
854 }
855
856 /* Successfully merged all elements. */
857 return true;
858}
859
860/* class program_state. */
861
862/* program_state's ctor. */
863
864program_state::program_state (const extrinsic_state &ext_state)
865: m_region_model (NULL),
866 m_checker_states (ext_state.get_num_checkers ()),
867 m_valid (true)
868{
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++)
874 {
875 sm_state_map *sm = new sm_state_map (ext_state.get_sm (idx: i));
876 m_checker_states.quick_push (obj: sm);
877 }
878}
879
880/* Attempt to use R to replay SUMMARY into this object.
881 Return true if it is possible. */
882
883bool
884sm_state_map::replay_call_summary (call_summary_replay &r,
885 const sm_state_map &summary)
886{
887 for (auto kv : summary.m_map)
888 {
889 const svalue *summary_sval = kv.first;
890 const svalue *caller_sval = r.convert_svalue_from_summary (summary_sval);
891 if (!caller_sval)
892 continue;
893 if (!caller_sval->can_have_associated_state_p ())
894 continue;
895 const svalue *summary_origin = kv.second.m_origin;
896 const svalue *caller_origin
897 = (summary_origin
898 ? r.convert_svalue_from_summary (summary_origin)
899 : NULL);
900 // caller_origin can be NULL.
901 m_map.put (k: caller_sval, v: entry_t (kv.second.m_state, caller_origin));
902 }
903 m_global_state = summary.m_global_state;
904 return true;
905}
906
907/* program_state's copy ctor. */
908
909program_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 ()),
912 m_valid (true)
913{
914 int i;
915 sm_state_map *smap;
916 FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
917 m_checker_states.quick_push (obj: smap->clone ());
918}
919
920/* program_state's assignment operator. */
921
922program_state&
923program_state::operator= (const program_state &other)
924{
925 delete m_region_model;
926 m_region_model = new region_model (*other.m_region_model);
927
928 int i;
929 sm_state_map *smap;
930 FOR_EACH_VEC_ELT (m_checker_states, i, smap)
931 delete smap;
932 m_checker_states.truncate (size: 0);
933 gcc_assert (m_checker_states.space (other.m_checker_states.length ()));
934
935 FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
936 m_checker_states.quick_push (obj: smap->clone ());
937
938 m_valid = other.m_valid;
939
940 return *this;
941}
942
943/* Move constructor for program_state (when building with C++11). */
944program_state::program_state (program_state &&other)
945: m_region_model (other.m_region_model),
946 m_checker_states (other.m_checker_states.length ())
947{
948 other.m_region_model = NULL;
949
950 int i;
951 sm_state_map *smap;
952 FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
953 m_checker_states.quick_push (obj: smap);
954 other.m_checker_states.truncate (size: 0);
955
956 m_valid = other.m_valid;
957}
958
959/* program_state's dtor. */
960
961program_state::~program_state ()
962{
963 delete m_region_model;
964}
965
966/* Generate a hash value for this program_state. */
967
968hashval_t
969program_state::hash () const
970{
971 hashval_t result = m_region_model->hash ();
972
973 int i;
974 sm_state_map *smap;
975 FOR_EACH_VEC_ELT (m_checker_states, i, smap)
976 result ^= smap->hash ();
977 return result;
978}
979
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
983 considered equal. */
984
985bool
986program_state::operator== (const program_state &other) const
987{
988 if (!(*m_region_model == *other.m_region_model))
989 return false;
990
991 int i;
992 sm_state_map *smap;
993 FOR_EACH_VEC_ELT (m_checker_states, i, smap)
994 if (!(*smap == *other.m_checker_states[i]))
995 return false;
996
997 gcc_checking_assert (hash () == other.hash ());
998
999 return true;
1000}
1001
1002/* Print a compact representation of this state to PP. */
1003
1004void
1005program_state::print (const extrinsic_state &ext_state,
1006 pretty_printer *pp) const
1007{
1008 pp_printf (pp, "rmodel: ");
1009 m_region_model->dump_to_pp (pp, simple: true, multiline: false);
1010 pp_newline (pp);
1011
1012 int i;
1013 sm_state_map *smap;
1014 FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1015 {
1016 if (!smap->is_empty_p ())
1017 {
1018 pp_printf (pp, "%s: ", ext_state.get_name (idx: i));
1019 smap->print (model: m_region_model, simple: true, multiline: false, pp);
1020 pp_newline (pp);
1021 }
1022 }
1023 if (!m_valid)
1024 {
1025 pp_printf (pp, "invalid state");
1026 pp_newline (pp);
1027 }
1028}
1029
1030/* Dump a representation of this state to PP. */
1031
1032void
1033program_state::dump_to_pp (const extrinsic_state &ext_state,
1034 bool /*summarize*/, bool multiline,
1035 pretty_printer *pp) const
1036{
1037 if (!multiline)
1038 pp_string (pp, "{");
1039 {
1040 pp_printf (pp, "rmodel:");
1041 if (multiline)
1042 pp_newline (pp);
1043 else
1044 pp_string (pp, " {");
1045 m_region_model->dump_to_pp (pp, simple: true, multiline);
1046 if (!multiline)
1047 pp_string (pp, "}");
1048 }
1049
1050 int i;
1051 sm_state_map *smap;
1052 FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1053 {
1054 if (!smap->is_empty_p ())
1055 {
1056 if (!multiline)
1057 pp_string (pp, " {");
1058 pp_printf (pp, "%s: ", ext_state.get_name (idx: i));
1059 if (multiline)
1060 pp_newline (pp);
1061 smap->print (model: m_region_model, simple: true, multiline, pp);
1062 if (!multiline)
1063 pp_string (pp, "}");
1064 }
1065 }
1066
1067 if (!m_valid)
1068 {
1069 if (!multiline)
1070 pp_space (pp);
1071 pp_printf (pp, "invalid state");
1072 if (multiline)
1073 pp_newline (pp);
1074 }
1075 if (!multiline)
1076 pp_string (pp, "}");
1077}
1078
1079/* Dump a representation of this state to OUTF. */
1080
1081void
1082program_state::dump_to_file (const extrinsic_state &ext_state,
1083 bool summarize, bool multiline,
1084 FILE *outf) const
1085{
1086 pretty_printer pp;
1087 pp_format_decoder (&pp) = default_tree_printer;
1088 if (outf == stderr)
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: &pp);
1092 pp_flush (&pp);
1093}
1094
1095/* Dump a multiline representation of this state to stderr. */
1096
1097DEBUG_FUNCTION void
1098program_state::dump (const extrinsic_state &ext_state,
1099 bool summarize) const
1100{
1101 dump_to_file (ext_state, summarize, multiline: true, stderr);
1102}
1103
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}. */
1110
1111json::object *
1112program_state::to_json (const extrinsic_state &ext_state) const
1113{
1114 json::object *state_obj = new json::object ();
1115
1116 state_obj->set (key: "store", v: m_region_model->get_store ()->to_json ());
1117 state_obj->set (key: "constraints",
1118 v: m_region_model->get_constraints ()->to_json ());
1119 if (m_region_model->get_current_frame ())
1120 state_obj->set (key: "curr_frame",
1121 v: m_region_model->get_current_frame ()->to_json ());
1122
1123 /* Provide m_checker_states as an object, using names as keys. */
1124 {
1125 json::object *checkers_obj = new json::object ();
1126
1127 int i;
1128 sm_state_map *smap;
1129 FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1130 if (!smap->is_empty_p ())
1131 checkers_obj->set (key: ext_state.get_name (idx: i), v: smap->to_json ());
1132
1133 state_obj->set (key: "checkers", v: checkers_obj);
1134 }
1135
1136 state_obj->set (key: "valid", v: new json::literal (m_valid));
1137
1138 return state_obj;
1139}
1140
1141/* Update this program_state to reflect a top-level call to FUN.
1142 The params will have initial_svalues. */
1143
1144void
1145program_state::push_frame (const extrinsic_state &ext_state ATTRIBUTE_UNUSED,
1146 const function &fun)
1147{
1148 m_region_model->push_frame (fun, NULL, NULL);
1149}
1150
1151/* Get the current function of this state. */
1152
1153const function *
1154program_state::get_current_function () const
1155{
1156 return m_region_model->get_current_function ();
1157}
1158
1159/* Determine if following edge SUCC from ENODE is valid within the graph EG
1160 and update this state accordingly in-place.
1161
1162 Return true if the edge can be followed, or false otherwise.
1163
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
1167 values.
1168
1169 This is the "state" half of exploded_node::on_edge. */
1170
1171bool
1172program_state::on_edge (exploded_graph &eg,
1173 exploded_node *enode,
1174 const superedge *succ,
1175 uncertainty_t *uncertainty)
1176{
1177 class my_path_context : public path_context
1178 {
1179 public:
1180 my_path_context (bool &terminated) : m_terminated (terminated) {}
1181 void bifurcate (std::unique_ptr<custom_edge_info>) final override
1182 {
1183 gcc_unreachable ();
1184 }
1185
1186 void terminate_path () final override
1187 {
1188 m_terminated = true;
1189 }
1190
1191 bool terminate_path_p () const final override
1192 {
1193 return m_terminated;
1194 }
1195 bool &m_terminated;
1196 };
1197
1198 /* Update state. */
1199 const program_point &point = enode->get_point ();
1200 const gimple *last_stmt = point.get_supernode ()->get_last_stmt ();
1201
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
1205 are impossible.
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 (),
1214 this,
1215 uncertainty, &path_ctxt,
1216 last_stmt);
1217 std::unique_ptr<rejected_constraint> rc;
1218 logger * const logger = eg.get_logger ();
1219 if (!m_region_model->maybe_update_for_edge (edge: *succ,
1220 last_stmt,
1221 ctxt: &ctxt,
1222 out: logger ? &rc : nullptr))
1223 {
1224 if (logger)
1225 {
1226 logger->start_log_line ();
1227 logger->log_partial (fmt: "edge to SN: %i is impossible"
1228 " due to region_model constraint: ",
1229 succ->m_dest->m_index);
1230 rc->dump_to_pp (pp: logger->get_printer ());
1231 logger->end_log_line ();
1232 }
1233 return false;
1234 }
1235 if (terminated)
1236 return false;
1237
1238 program_state::detect_leaks (src_state: enode->get_state (), dest_state: *this,
1239 NULL, ext_state: eg.get_ext_state (),
1240 ctxt: &ctxt);
1241
1242 return true;
1243}
1244
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 ) */
1249void
1250program_state::push_call (exploded_graph &eg,
1251 exploded_node *enode,
1252 const gcall *call_stmt,
1253 uncertainty_t *uncertainty)
1254{
1255 /* Update state. */
1256 const program_point &point = enode->get_point ();
1257 const gimple *last_stmt = point.get_supernode ()->get_last_stmt ();
1258
1259 impl_region_model_context ctxt (eg, enode,
1260 &enode->get_state (),
1261 this,
1262 uncertainty,
1263 NULL,
1264 last_stmt);
1265 m_region_model->update_for_gcall (call_stmt, ctxt: &ctxt);
1266}
1267
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
1271 the return */
1272void
1273program_state::returning_call (exploded_graph &eg,
1274 exploded_node *enode,
1275 const gcall *call_stmt,
1276 uncertainty_t *uncertainty)
1277{
1278 /* Update state. */
1279 const program_point &point = enode->get_point ();
1280 const gimple *last_stmt = point.get_supernode ()->get_last_stmt ();
1281
1282 impl_region_model_context ctxt (eg, enode,
1283 &enode->get_state (),
1284 this,
1285 uncertainty,
1286 NULL,
1287 last_stmt);
1288 m_region_model->update_for_return_gcall (call_stmt, ctxt: &ctxt);
1289}
1290
1291/* Generate a simpler version of THIS, discarding state that's no longer
1292 relevant at POINT.
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). */
1296
1297program_state
1298program_state::prune_for_point (exploded_graph &eg,
1299 const program_point &point,
1300 exploded_node *enode_for_diag,
1301 uncertainty_t *uncertainty) const
1302{
1303 logger * const logger = eg.get_logger ();
1304 LOG_SCOPE (logger);
1305
1306 function *fun = point.get_function ();
1307 if (!fun)
1308 return *this;
1309
1310 program_state new_state (*this);
1311
1312 const state_purge_map *pm = eg.get_purge_map ();
1313 if (pm)
1314 {
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 (out: &regs);
1319 regs.qsort (region::cmp_ptr_ptr);
1320 unsigned i;
1321 const decl_region *reg;
1322 FOR_EACH_VEC_ELT (regs, i, reg)
1323 {
1324 const tree node = reg->get_decl ();
1325 if (TREE_CODE (node) == SSA_NAME)
1326 {
1327 const tree ssa_name = node;
1328 const state_purge_per_ssa_name &per_ssa
1329 = pm->get_data_for_ssa_name (name: node);
1330 if (!per_ssa.needed_at_point_p (point: point.get_function_point ()))
1331 {
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.
1336
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
1342 popped. */
1343 const svalue *sval
1344 = new_state.m_region_model->get_store_value (reg, NULL);
1345 if (!new_state.can_purge_p (ext_state: eg.get_ext_state (), sval)
1346 && SSA_NAME_VAR (ssa_name))
1347 {
1348 /* (currently only state maps can keep things
1349 alive). */
1350 if (logger)
1351 logger->log (fmt: "not purging binding for %qE"
1352 " (used by state map)", ssa_name);
1353 continue;
1354 }
1355
1356 new_state.m_region_model->purge_region (reg);
1357 num_ssas_purged++;
1358 }
1359 }
1360 else
1361 {
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: point.get_function_point ()))
1369 {
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
1374 referred to. */
1375 if (!new_state.can_purge_base_region_p (ext_state: eg.get_ext_state (),
1376 base_reg: reg))
1377 {
1378 /* (currently only state maps can keep things
1379 alive). */
1380 if (logger)
1381 logger->log (fmt: "not purging binding for %qE"
1382 " (value in binding used by state map)",
1383 decl);
1384 continue;
1385 }
1386
1387 new_state.m_region_model->purge_region (reg);
1388 num_decls_purged++;
1389 }
1390 }
1391 }
1392
1393 if (num_ssas_purged > 0 || num_decls_purged > 0)
1394 {
1395 if (logger)
1396 {
1397 logger->log (fmt: "num_ssas_purged: %i", num_ssas_purged);
1398 logger->log (fmt: "num_decl_purged: %i", num_decls_purged);
1399 }
1400 impl_region_model_context ctxt (eg, enode_for_diag,
1401 this,
1402 &new_state,
1403 uncertainty, NULL,
1404 point.get_stmt ());
1405 detect_leaks (src_state: *this, dest_state: new_state, NULL, ext_state: eg.get_ext_state (), ctxt: &ctxt);
1406 }
1407 }
1408
1409 new_state.m_region_model->canonicalize ();
1410
1411 return new_state;
1412}
1413
1414/* Return true if there are no unpurgeable bindings within BASE_REG. */
1415
1416bool
1417program_state::can_purge_base_region_p (const extrinsic_state &ext_state,
1418 const region *base_reg) const
1419{
1420 binding_cluster *cluster
1421 = m_region_model->get_store ()->get_cluster (base_reg);
1422 if (!cluster)
1423 return true;
1424
1425 for (auto iter : *cluster)
1426 {
1427 const svalue *sval = iter.second;
1428 if (!can_purge_p (ext_state, sval))
1429 return false;
1430 }
1431
1432 return true;
1433}
1434
1435/* Get a representative tree to use for describing SVAL. */
1436
1437tree
1438program_state::get_representative_tree (const svalue *sval) const
1439{
1440 gcc_assert (m_region_model);
1441 return m_region_model->get_representative_tree (sval);
1442}
1443
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. */
1447
1448bool
1449program_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
1453{
1454 gcc_assert (out);
1455 gcc_assert (m_region_model);
1456
1457 /* Attempt to merge the sm-states. */
1458 int i;
1459 sm_state_map *smap;
1460 FOR_EACH_VEC_ELT (out->m_checker_states, i, smap)
1461 if (!m_checker_states[i]->can_merge_with_p (other: *other.m_checker_states[i],
1462 sm: ext_state.get_sm (idx: i),
1463 ext_state,
1464 out: &out->m_checker_states[i]))
1465 return false;
1466
1467 /* Attempt to merge the region_models. */
1468 if (!m_region_model->can_merge_with_p (other_model: *other.m_region_model,
1469 point,
1470 out_model: out->m_region_model,
1471 ext_state: &ext_state,
1472 state_a: this, state_b: &other))
1473 return false;
1474
1475 out->m_region_model->canonicalize ();
1476
1477 return true;
1478}
1479
1480/* Assert that this object is valid. */
1481
1482void
1483program_state::validate (const extrinsic_state &ext_state) const
1484{
1485 /* Skip this in a release build. */
1486#if !CHECKING_P
1487 return;
1488#endif
1489
1490 gcc_assert (m_checker_states.length () == ext_state.get_num_checkers ());
1491 m_region_model->validate ();
1492}
1493
1494static void
1495log_set_of_svalues (logger *logger, const char *name,
1496 const svalue_set &set)
1497{
1498 logger->log (fmt: name);
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 (obj: *iter);
1504 sval_vecs.qsort (svalue::cmp_ptr_ptr);
1505 unsigned i;
1506 const svalue *sval;
1507 FOR_EACH_VEC_ELT (sval_vecs, i, sval)
1508 {
1509 logger->start_log_line ();
1510 pretty_printer *pp = logger->get_printer ();
1511 if (!flag_dump_noaddr)
1512 {
1513 pp_pointer (pp, sval);
1514 pp_string (pp, ": ");
1515 }
1516 sval->dump_to_pp (pp, simple: false);
1517 logger->end_log_line ();
1518 }
1519 logger->dec_indent ();
1520}
1521
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.
1526
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.
1530
1531 This function should be called at each fine-grained state change, not
1532 just at exploded edges. */
1533
1534void
1535program_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)
1540{
1541 logger *logger = ext_state.get_logger ();
1542 LOG_SCOPE (logger);
1543 const uncertainty_t *uncertainty = ctxt->get_uncertainty ();
1544 if (logger)
1545 {
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, multiline: 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, multiline: false, pp);
1554 logger->end_log_line ();
1555 if (extra_sval)
1556 {
1557 logger->start_log_line ();
1558 pp_string (pp, "extra_sval: ");
1559 extra_sval->dump_to_pp (pp, simple: true);
1560 logger->end_log_line ();
1561 }
1562 if (uncertainty)
1563 {
1564 logger->start_log_line ();
1565 pp_string (pp, "uncertainty: ");
1566 uncertainty->dump_to_pp (pp, simple: true);
1567 logger->end_log_line ();
1568 }
1569 }
1570
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 (out: &known_src_svalues,
1577 NULL, NULL);
1578 svalue_set maybe_dest_svalues;
1579 dest_state.m_region_model->get_reachable_svalues (out: &maybe_dest_svalues,
1580 extra_sval, uncertainty);
1581
1582 if (logger)
1583 {
1584 log_set_of_svalues (logger, name: "src_state known reachable svalues:",
1585 set: known_src_svalues);
1586 log_set_of_svalues (logger, name: "dest_state maybe reachable svalues:",
1587 set: maybe_dest_svalues);
1588 }
1589
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)
1593 {
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 (live_svalues: &maybe_dest_svalues, model: dest_state.m_region_model))
1602 dead_svals.quick_push (obj: sval);
1603 }
1604
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);
1608 unsigned i;
1609 const svalue *sval;
1610 FOR_EACH_VEC_ELT (dead_svals, i, sval)
1611 ctxt->on_svalue_leak (sval);
1612
1613 /* Purge dead svals from sm-state. */
1614 ctxt->on_liveness_change (live_svalues: maybe_dest_svalues,
1615 model: dest_state.m_region_model);
1616
1617 /* Purge dead svals from constraints. */
1618 dest_state.m_region_model->get_constraints ()->on_liveness_change
1619 (live_svalues: maybe_dest_svalues, model: dest_state.m_region_model);
1620
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);
1626}
1627
1628/* Attempt to use R to replay SUMMARY into this object.
1629 Return true if it is possible. */
1630
1631bool
1632program_state::replay_call_summary (call_summary_replay &r,
1633 const program_state &summary)
1634{
1635 if (!m_region_model->replay_call_summary (r, summary: *summary.m_region_model))
1636 return false;
1637
1638 for (unsigned sm_idx = 0; sm_idx < m_checker_states.length (); sm_idx++)
1639 {
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: *summary_sm_map);
1642 }
1643
1644 if (!summary.m_valid)
1645 m_valid = false;
1646
1647 return true;
1648}
1649
1650/* Handle calls to "__analyzer_dump_state". */
1651
1652void
1653program_state::impl_call_analyzer_dump_state (const gcall *call,
1654 const extrinsic_state &ext_state,
1655 region_model_context *ctxt)
1656{
1657 call_details cd (call, m_region_model, ctxt);
1658 const char *sm_name = cd.get_arg_string_literal (idx: 0);
1659 if (!sm_name)
1660 {
1661 error_at (call->location, "cannot determine state machine");
1662 return;
1663 }
1664 unsigned sm_idx;
1665 if (!ext_state.get_sm_idx_by_name (name: sm_name, out: &sm_idx))
1666 {
1667 error_at (call->location, "unrecognized state machine %qs", sm_name);
1668 return;
1669 }
1670 const sm_state_map *smap = m_checker_states[sm_idx];
1671
1672 const svalue *sval = cd.get_arg_svalue (idx: 1);
1673
1674 /* Strip off cast to int (due to variadic args). */
1675 if (const svalue *cast = sval->maybe_undo_cast ())
1676 sval = cast;
1677
1678 state_machine::state_t state = smap->get_state (sval, ext_state);
1679 warning_at (call->location, 0, "state: %qs", state->get_name ());
1680}
1681
1682#if CHECKING_P
1683
1684namespace selftest {
1685
1686/* Tests for sm_state_map. */
1687
1688static void
1689test_sm_state_map ()
1690{
1691 tree x = build_global_decl (name: "x", integer_type_node);
1692 tree y = build_global_decl (name: "y", integer_type_node);
1693 tree z = build_global_decl (name: "z", integer_type_node);
1694
1695 state_machine *sm = make_malloc_state_machine (NULL);
1696 auto_delete_vec <state_machine> checkers;
1697 checkers.safe_push (obj: sm);
1698 engine eng;
1699 extrinsic_state ext_state (checkers, &eng);
1700 state_machine::state_t start = sm->get_start_state ();
1701
1702 /* Test setting states on svalue_id instances directly. */
1703 {
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 (expr: x, NULL);
1709 const svalue *y_sval = model.get_rvalue (expr: y, NULL);
1710 const svalue *z_sval = model.get_rvalue (expr: z, NULL);
1711
1712 sm_state_map map (*sm);
1713 ASSERT_TRUE (map.is_empty_p ());
1714 ASSERT_EQ (map.get_state (x_sval, ext_state), start);
1715
1716 map.impl_set_state (sval: x_sval, state: TEST_STATE_42, origin: 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 ());
1721
1722 map.impl_set_state (sval: y_sval, state: 0, origin: z_sval, ext_state);
1723 ASSERT_EQ (map.get_state (y_sval, ext_state), start);
1724
1725 map.impl_set_state (sval: x_sval, state: 0, origin: z_sval, ext_state);
1726 ASSERT_EQ (map.get_state (x_sval, ext_state), start);
1727 ASSERT_TRUE (map.is_empty_p ());
1728 }
1729
1730 const state_machine::state test_state_5 ("test state 5", 5);
1731 const state_machine::state_t TEST_STATE_5 = &test_state_5;
1732
1733 /* Test setting states via equivalence classes. */
1734 {
1735 region_model_manager mgr;
1736 region_model model (&mgr);
1737 const svalue *x_sval = model.get_rvalue (expr: x, NULL);
1738 const svalue *y_sval = model.get_rvalue (expr: y, NULL);
1739 const svalue *z_sval = model.get_rvalue (expr: z, NULL);
1740
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);
1745
1746 model.add_constraint (lhs: x, op: EQ_EXPR, rhs: y, NULL);
1747
1748 /* Setting x to a state should also update y, as they
1749 are in the same equivalence class. */
1750 map.set_state (model: &model, sval: x_sval, state: TEST_STATE_5, origin: 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);
1755 }
1756
1757 /* Test equality and hashing. */
1758 {
1759 region_model_manager mgr;
1760 region_model model (&mgr);
1761 const svalue *y_sval = model.get_rvalue (expr: y, NULL);
1762 const svalue *z_sval = model.get_rvalue (expr: z, NULL);
1763
1764 sm_state_map map0 (*sm);
1765 sm_state_map map1 (*sm);
1766 sm_state_map map2 (*sm);
1767
1768 ASSERT_EQ (map0.hash (), map1.hash ());
1769 ASSERT_EQ (map0, map1);
1770
1771 map1.impl_set_state (sval: y_sval, state: TEST_STATE_5, origin: z_sval, ext_state);
1772 ASSERT_NE (map0.hash (), map1.hash ());
1773 ASSERT_NE (map0, map1);
1774
1775 /* Make the same change to map2. */
1776 map2.impl_set_state (sval: y_sval, state: TEST_STATE_5, origin: z_sval, ext_state);
1777 ASSERT_EQ (map1.hash (), map2.hash ());
1778 ASSERT_EQ (map1, map2);
1779 }
1780
1781 /* Equality and hashing shouldn't depend on ordering. */
1782 {
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);
1790
1791 ASSERT_EQ (map0.hash (), map1.hash ());
1792 ASSERT_EQ (map0, map1);
1793
1794 region_model_manager mgr;
1795 region_model model (&mgr);
1796 const svalue *x_sval = model.get_rvalue (expr: x, NULL);
1797 const svalue *y_sval = model.get_rvalue (expr: y, NULL);
1798 const svalue *z_sval = model.get_rvalue (expr: z, NULL);
1799
1800 map1.impl_set_state (sval: x_sval, state: TEST_STATE_2, NULL, ext_state);
1801 map1.impl_set_state (sval: y_sval, state: TEST_STATE_3, NULL, ext_state);
1802 map1.impl_set_state (sval: z_sval, state: TEST_STATE_2, NULL, ext_state);
1803
1804 map2.impl_set_state (sval: z_sval, state: TEST_STATE_2, NULL, ext_state);
1805 map2.impl_set_state (sval: y_sval, state: TEST_STATE_3, NULL, ext_state);
1806 map2.impl_set_state (sval: x_sval, state: TEST_STATE_2, NULL, ext_state);
1807
1808 ASSERT_EQ (map1.hash (), map2.hash ());
1809 ASSERT_EQ (map1, map2);
1810 }
1811
1812 // TODO: coverage for purging
1813}
1814
1815/* Check program_state works as expected. */
1816
1817static void
1818test_program_state_1 ()
1819{
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 (name: "p", ptr_type_node);
1823
1824 state_machine *sm = make_malloc_state_machine (NULL);
1825 const state_machine::state_t UNCHECKED_STATE
1826 = sm->get_state_by_name (name: "unchecked");
1827 auto_delete_vec <state_machine> checkers;
1828 checkers.safe_push (obj: sm);
1829
1830 engine eng;
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, pointee: new_reg);
1840 model->set_value (lhs_reg: model->get_lvalue (expr: p, NULL),
1841 rhs_sval: ptr_sval, NULL);
1842 sm_state_map *smap = s.m_checker_states[0];
1843
1844 smap->impl_set_state (sval: ptr_sval, state: UNCHECKED_STATE, NULL, ext_state);
1845 ASSERT_EQ (smap->get_state (ptr_sval, ext_state), UNCHECKED_STATE);
1846}
1847
1848/* Check that program_state works for string literals. */
1849
1850static void
1851test_program_state_2 ()
1852{
1853 /* Create a program_state for a global ptr "p" that points to
1854 a string constant. */
1855 tree p = build_global_decl (name: "p", ptr_type_node);
1856
1857 tree string_cst_ptr = build_string_literal (4, "foo");
1858
1859 auto_delete_vec <state_machine> checkers;
1860 engine eng;
1861 extrinsic_state ext_state (checkers, &eng);
1862
1863 program_state s (ext_state);
1864 region_model *model = s.m_region_model;
1865 const region *p_reg = model->get_lvalue (expr: p, NULL);
1866 const svalue *str_sval = model->get_rvalue (expr: string_cst_ptr, NULL);
1867 model->set_value (lhs_reg: p_reg, rhs_sval: str_sval, NULL);
1868}
1869
1870/* Verify that program_states with identical sm-state can be merged,
1871 and that the merged program_state preserves the sm-state. */
1872
1873static void
1874test_program_state_merging ()
1875{
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 (name: "p", ptr_type_node);
1879
1880 engine eng;
1881 region_model_manager *mgr = eng.get_model_manager ();
1882 program_point point (program_point::origin (mgr: *mgr));
1883 auto_delete_vec <state_machine> checkers;
1884 checkers.safe_push (obj: make_malloc_state_machine (NULL));
1885 extrinsic_state ext_state (checkers, &eng);
1886
1887 program_state s0 (ext_state);
1888 uncertainty_t uncertainty;
1889 impl_region_model_context ctxt (&s0, ext_state, &uncertainty);
1890
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, pointee: new_reg);
1897 model0->set_value (lhs_reg: model0->get_lvalue (expr: p, ctxt: &ctxt),
1898 rhs_sval: ptr_sval, ctxt: &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 (sval: ptr_sval, state: TEST_STATE, NULL, ext_state);
1903 ASSERT_EQ (smap->get_state (ptr_sval, ext_state), TEST_STATE);
1904
1905 model0->canonicalize ();
1906
1907 /* Verify that canonicalization preserves sm-state. */
1908 ASSERT_EQ (smap->get_state (model0->get_rvalue (p, NULL), ext_state),
1909 TEST_STATE);
1910
1911 /* Make a copy of the program_state. */
1912 program_state s1 (s0);
1913 ASSERT_EQ (s0, s1);
1914
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);
1921
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),
1926 ext_state),
1927 TEST_STATE);
1928
1929 /* Try canonicalizing. */
1930 merged.m_region_model->canonicalize ();
1931 merged.validate (ext_state);
1932
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),
1935 ext_state),
1936 TEST_STATE);
1937
1938 /* After canonicalization, we ought to have equality with the inputs. */
1939 ASSERT_EQ (s0, merged);
1940}
1941
1942/* Verify that program_states with different global-state in an sm-state
1943 can't be merged. */
1944
1945static void
1946test_program_state_merging_2 ()
1947{
1948 engine eng;
1949 region_model_manager *mgr = eng.get_model_manager ();
1950 program_point point (program_point::origin (mgr: *mgr));
1951 auto_delete_vec <state_machine> checkers;
1952 checkers.safe_push (obj: make_signal_state_machine (NULL));
1953 extrinsic_state ext_state (checkers, &eng);
1954
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;
1959
1960 program_state s0 (ext_state);
1961 {
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);
1965 }
1966
1967 program_state s1 (ext_state);
1968 {
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);
1972 }
1973
1974 ASSERT_NE (s0, s1);
1975
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));
1979}
1980
1981/* Run all of the selftests within this file. */
1982
1983void
1984analyzer_program_state_cc_tests ()
1985{
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 ();
1991}
1992
1993} // namespace selftest
1994
1995#endif /* CHECKING_P */
1996
1997} // namespace ana
1998
1999#endif /* #if ENABLE_ANALYZER */
2000

source code of gcc/analyzer/program-state.cc