Line data Source code
1 : /* Classes for representing the state of interest at a given path of analysis.
2 : Copyright (C) 2019-2026 Free Software Foundation, Inc.
3 : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
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)
10 : any later version.
11 :
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.
16 :
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/>. */
20 :
21 : #include "analyzer/common.h"
22 :
23 : #include "sbitmap.h"
24 : #include "ordered-hash-map.h"
25 : #include "selftest.h"
26 : #include "cfg.h"
27 : #include "gimple-iterator.h"
28 : #include "cgraph.h"
29 : #include "digraph.h"
30 : #include "diagnostics/event-id.h"
31 : #include "diagnostics/state-graphs.h"
32 : #include "graphviz.h"
33 :
34 : #include "text-art/tree-widget.h"
35 : #include "text-art/dump.h"
36 :
37 : #include "analyzer/analyzer-logging.h"
38 : #include "analyzer/sm.h"
39 : #include "analyzer/call-string.h"
40 : #include "analyzer/program-point.h"
41 : #include "analyzer/store.h"
42 : #include "analyzer/region-model.h"
43 : #include "analyzer/program-state.h"
44 : #include "analyzer/constraint-manager.h"
45 : #include "analyzer/pending-diagnostic.h"
46 : #include "analyzer/diagnostic-manager.h"
47 : #include "analyzer/supergraph.h"
48 : #include "analyzer/program-state.h"
49 : #include "analyzer/exploded-graph.h"
50 : #include "analyzer/state-purge.h"
51 : #include "analyzer/call-summary.h"
52 : #include "analyzer/analyzer-selftests.h"
53 : #include "analyzer/ana-state-to-diagnostic-state.h"
54 :
55 : #if ENABLE_ANALYZER
56 :
57 : namespace ana {
58 :
59 : /* class extrinsic_state. */
60 :
61 : /* Dump a multiline representation of this state to PP. */
62 :
63 : void
64 0 : extrinsic_state::dump_to_pp (pretty_printer *pp) const
65 : {
66 0 : pp_printf (pp, "extrinsic_state: %i checker(s)\n", get_num_checkers ());
67 0 : unsigned i = 0;
68 0 : for (auto &checker : m_checkers)
69 : {
70 0 : pp_printf (pp, "m_checkers[%i]: %qs\n", ++i, checker->get_name ());
71 0 : checker->dump_to_pp (pp);
72 : }
73 0 : }
74 :
75 : /* Dump a multiline representation of this state to OUTF. */
76 :
77 : void
78 0 : extrinsic_state::dump_to_file (FILE *outf) const
79 : {
80 0 : tree_dump_pretty_printer pp (outf);
81 0 : dump_to_pp (&pp);
82 0 : }
83 :
84 : /* Dump a multiline representation of this state to stderr. */
85 :
86 : DEBUG_FUNCTION void
87 0 : extrinsic_state::dump () const
88 : {
89 0 : dump_to_file (stderr);
90 0 : }
91 :
92 : /* Return a new json::object of the form
93 : {"checkers" : array of objects, one for each state_machine}. */
94 :
95 : std::unique_ptr<json::object>
96 0 : extrinsic_state::to_json () const
97 : {
98 0 : auto ext_state_obj = std::make_unique<json::object> ();
99 :
100 0 : {
101 0 : auto checkers_arr = std::make_unique<json::array> ();
102 0 : for (auto &sm : m_checkers)
103 0 : checkers_arr->append (sm->to_json ());
104 0 : ext_state_obj->set ("checkers", std::move (checkers_arr));
105 0 : }
106 :
107 0 : return ext_state_obj;
108 : }
109 :
110 : /* Get the region_model_manager for this extrinsic_state. */
111 :
112 : region_model_manager *
113 16712170 : extrinsic_state::get_model_manager () const
114 : {
115 16712170 : if (m_engine)
116 16712170 : return m_engine->get_model_manager ();
117 : else
118 : return nullptr; /* for selftests. */
119 : }
120 :
121 : /* Try to find a state machine named NAME.
122 : If found, return true and write its index to *OUT.
123 : Otherwise return false. */
124 :
125 : bool
126 781030 : extrinsic_state::get_sm_idx_by_name (const char *name, unsigned *out) const
127 : {
128 3121277 : for (size_t i = 0; i < m_checkers.size (); ++i)
129 3120797 : if (0 == strcmp (name, m_checkers[i]->get_name ()))
130 : {
131 : /* Found NAME. */
132 780550 : *out = i;
133 780550 : return true;
134 : }
135 :
136 : /* NAME not found. */
137 : return false;
138 : }
139 :
140 : /* struct sm_state_map::entry_t. */
141 :
142 : int
143 661734 : sm_state_map::entry_t::cmp (const entry_t &entry_a, const entry_t &entry_b)
144 : {
145 661734 : gcc_assert (entry_a.m_state);
146 661734 : gcc_assert (entry_b.m_state);
147 661734 : if (int cmp_state = ((int)entry_a.m_state->get_id ()
148 661734 : - (int)entry_b.m_state->get_id ()))
149 : return cmp_state;
150 653346 : if (entry_a.m_origin && entry_b.m_origin)
151 0 : return svalue::cmp_ptr (entry_a.m_origin, entry_b.m_origin);
152 653346 : if (entry_a.m_origin)
153 : return 1;
154 653346 : if (entry_b.m_origin)
155 0 : return -1;
156 : return 0;
157 : }
158 :
159 : /* class sm_state_map. */
160 :
161 : /* sm_state_map's ctor. */
162 :
163 2798720 : sm_state_map::sm_state_map (const state_machine &sm)
164 2798720 : : m_sm (sm), m_map (), m_global_state (sm.get_start_state ())
165 : {
166 2798720 : }
167 :
168 : /* Clone the sm_state_map. */
169 :
170 : sm_state_map *
171 15600649 : sm_state_map::clone () const
172 : {
173 15600649 : return new sm_state_map (*this);
174 : }
175 :
176 : /* Print this sm_state_map to PP.
177 : If MODEL is non-NULL, print representative tree values where
178 : available. */
179 :
180 : void
181 413 : sm_state_map::print (const region_model *model,
182 : bool simple, bool multiline,
183 : pretty_printer *pp) const
184 : {
185 413 : bool first = true;
186 413 : if (!multiline)
187 101 : pp_string (pp, "{");
188 413 : if (m_global_state != m_sm.get_start_state ())
189 : {
190 0 : if (multiline)
191 0 : pp_string (pp, " ");
192 0 : pp_string (pp, "global: ");
193 0 : m_global_state->dump_to_pp (pp);
194 0 : if (multiline)
195 0 : pp_newline (pp);
196 : first = false;
197 : }
198 413 : auto_vec <const svalue *> keys (m_map.elements ());
199 413 : for (map_t::iterator iter = m_map.begin ();
200 1092 : iter != m_map.end ();
201 679 : ++iter)
202 679 : keys.quick_push ((*iter).first);
203 413 : keys.qsort (svalue::cmp_ptr_ptr);
204 413 : unsigned i;
205 413 : const svalue *sval;
206 1505 : FOR_EACH_VEC_ELT (keys, i, sval)
207 : {
208 679 : if (multiline)
209 560 : pp_string (pp, " ");
210 119 : else if (!first)
211 18 : pp_string (pp, ", ");
212 679 : first = false;
213 679 : if (!flag_dump_noaddr)
214 : {
215 679 : pp_pointer (pp, sval);
216 679 : pp_string (pp, ": ");
217 : }
218 679 : sval->dump_to_pp (pp, simple);
219 :
220 679 : entry_t e = *const_cast <map_t &> (m_map).get (sval);
221 679 : pp_string (pp, ": ");
222 679 : e.m_state->dump_to_pp (pp);
223 679 : if (model)
224 679 : if (tree rep = model->get_representative_tree (sval))
225 : {
226 653 : pp_string (pp, " (");
227 653 : dump_quoted_tree (pp, rep);
228 653 : pp_character (pp, ')');
229 : }
230 679 : if (e.m_origin)
231 : {
232 0 : pp_string (pp, " (origin: ");
233 0 : if (!flag_dump_noaddr)
234 : {
235 0 : pp_pointer (pp, e.m_origin);
236 0 : pp_string (pp, ": ");
237 : }
238 0 : e.m_origin->dump_to_pp (pp, simple);
239 0 : if (model)
240 0 : if (tree rep = model->get_representative_tree (e.m_origin))
241 : {
242 0 : pp_string (pp, " (");
243 0 : dump_quoted_tree (pp, rep);
244 0 : pp_character (pp, ')');
245 : }
246 0 : pp_string (pp, ")");
247 : }
248 679 : if (multiline)
249 560 : pp_newline (pp);
250 : }
251 413 : if (!multiline)
252 101 : pp_string (pp, "}");
253 413 : }
254 :
255 : /* Dump this object to stderr. */
256 :
257 : DEBUG_FUNCTION void
258 0 : sm_state_map::dump (bool simple) const
259 : {
260 0 : tree_dump_pretty_printer pp (stderr);
261 0 : print (nullptr, simple, true, &pp);
262 0 : pp_newline (&pp);
263 0 : }
264 :
265 : /* Return a new json::object of the form
266 : {"global" : (optional) value for global state,
267 : SVAL_DESC : value for state}. */
268 :
269 : std::unique_ptr<json::object>
270 0 : sm_state_map::to_json () const
271 : {
272 0 : auto map_obj = std::make_unique<json::object> ();
273 :
274 0 : if (m_global_state != m_sm.get_start_state ())
275 0 : map_obj->set ("global", m_global_state->to_json ());
276 0 : for (map_t::iterator iter = m_map.begin ();
277 0 : iter != m_map.end ();
278 0 : ++iter)
279 : {
280 0 : const svalue *sval = (*iter).first;
281 0 : entry_t e = (*iter).second;
282 :
283 0 : label_text sval_desc = sval->get_desc ();
284 0 : map_obj->set (sval_desc.get (), e.m_state->to_json ());
285 :
286 : /* This doesn't yet JSONify e.m_origin. */
287 0 : }
288 0 : return map_obj;
289 : }
290 :
291 : /* Make a text_art::tree_widget describing this sm_state_map,
292 : using MODEL if non-null to describe svalues. */
293 :
294 : std::unique_ptr<text_art::tree_widget>
295 0 : sm_state_map::make_dump_widget (const text_art::dump_widget_info &dwi,
296 : const region_model *model) const
297 : {
298 0 : using text_art::styled_string;
299 0 : using text_art::tree_widget;
300 0 : std::unique_ptr<tree_widget> state_widget
301 : (tree_widget::from_fmt (dwi, nullptr,
302 0 : "%qs state machine", m_sm.get_name ()));
303 :
304 0 : if (m_global_state != m_sm.get_start_state ())
305 : {
306 0 : pretty_printer the_pp;
307 0 : pretty_printer * const pp = &the_pp;
308 0 : pp_format_decoder (pp) = default_tree_printer;
309 0 : pp_string (pp, "Global State: ");
310 0 : m_global_state->dump_to_pp (pp);
311 0 : state_widget->add_child (tree_widget::make (dwi, pp));
312 0 : }
313 :
314 0 : auto_vec <const svalue *> keys (m_map.elements ());
315 0 : for (map_t::iterator iter = m_map.begin ();
316 0 : iter != m_map.end ();
317 0 : ++iter)
318 0 : keys.quick_push ((*iter).first);
319 0 : keys.qsort (svalue::cmp_ptr_ptr);
320 0 : unsigned i;
321 0 : const svalue *sval;
322 0 : FOR_EACH_VEC_ELT (keys, i, sval)
323 : {
324 0 : pretty_printer the_pp;
325 0 : pretty_printer * const pp = &the_pp;
326 0 : const bool simple = true;
327 0 : pp_format_decoder (pp) = default_tree_printer;
328 0 : if (!flag_dump_noaddr)
329 : {
330 0 : pp_pointer (pp, sval);
331 0 : pp_string (pp, ": ");
332 : }
333 0 : sval->dump_to_pp (pp, simple);
334 :
335 0 : entry_t e = *const_cast <map_t &> (m_map).get (sval);
336 0 : pp_string (pp, ": ");
337 0 : e.m_state->dump_to_pp (pp);
338 0 : if (model)
339 0 : if (tree rep = model->get_representative_tree (sval))
340 : {
341 0 : pp_string (pp, " (");
342 0 : dump_quoted_tree (pp, rep);
343 0 : pp_character (pp, ')');
344 : }
345 0 : if (e.m_origin)
346 : {
347 0 : pp_string (pp, " (origin: ");
348 0 : if (!flag_dump_noaddr)
349 : {
350 0 : pp_pointer (pp, e.m_origin);
351 0 : pp_string (pp, ": ");
352 : }
353 0 : e.m_origin->dump_to_pp (pp, simple);
354 0 : if (model)
355 0 : if (tree rep = model->get_representative_tree (e.m_origin))
356 : {
357 0 : pp_string (pp, " (");
358 0 : dump_quoted_tree (pp, rep);
359 0 : pp_character (pp, ')');
360 : }
361 0 : pp_string (pp, ")");
362 : }
363 :
364 0 : state_widget->add_child (tree_widget::make (dwi, pp));
365 0 : }
366 :
367 0 : return state_widget;
368 0 : }
369 :
370 : /* Return true if no states have been set within this map
371 : (all expressions are for the start state). */
372 :
373 : bool
374 12252 : sm_state_map::is_empty_p () const
375 : {
376 12252 : return m_map.elements () == 0 && m_global_state == m_sm.get_start_state ();
377 : }
378 :
379 : /* Generate a hash value for this sm_state_map. */
380 :
381 : hashval_t
382 6250678 : sm_state_map::hash () const
383 : {
384 6250678 : hashval_t result = 0;
385 :
386 : /* Accumulate the result by xoring a hash for each slot, so that the
387 : result doesn't depend on the ordering of the slots in the map. */
388 :
389 6250678 : for (map_t::iterator iter = m_map.begin ();
390 8561260 : iter != m_map.end ();
391 2310582 : ++iter)
392 : {
393 2310582 : inchash::hash hstate;
394 2310582 : hstate.add_ptr ((*iter).first);
395 2310582 : entry_t e = (*iter).second;
396 2310582 : hstate.add_int (e.m_state->get_id ());
397 2310582 : hstate.add_ptr (e.m_origin);
398 2310582 : result ^= hstate.end ();
399 : }
400 6250678 : result ^= m_global_state->get_id ();
401 :
402 6250678 : return result;
403 : }
404 :
405 : /* Equality operator for sm_state_map. */
406 :
407 : bool
408 1694885 : sm_state_map::operator== (const sm_state_map &other) const
409 : {
410 1694885 : if (m_global_state != other.m_global_state)
411 : return false;
412 :
413 1693875 : if (m_map.elements () != other.m_map.elements ())
414 : return false;
415 :
416 1467939 : for (map_t::iterator iter = m_map.begin ();
417 2288601 : iter != m_map.end ();
418 820662 : ++iter)
419 : {
420 846644 : const svalue *sval = (*iter).first;
421 846644 : entry_t e = (*iter).second;
422 846644 : entry_t *other_slot = const_cast <map_t &> (other.m_map).get (sval);
423 846644 : if (other_slot == nullptr)
424 25982 : return false;
425 1667306 : if (e != *other_slot)
426 : return false;
427 : }
428 :
429 1441957 : gcc_checking_assert (hash () == other.hash ());
430 :
431 : return true;
432 : }
433 :
434 : /* Get the state of SVAL within this object.
435 : States default to the start state. */
436 :
437 : state_machine::state_t
438 12397234 : sm_state_map::get_state (const svalue *sval,
439 : const extrinsic_state &ext_state) const
440 : {
441 12397234 : gcc_assert (sval);
442 :
443 12397234 : sval = canonicalize_svalue (sval, ext_state);
444 :
445 24794468 : if (entry_t *slot
446 12397234 : = const_cast <map_t &> (m_map).get (sval))
447 912024 : return slot->m_state;
448 :
449 : /* SVAL has no explicit sm-state.
450 : If this sm allows for state inheritance, then SVAL might have implicit
451 : sm-state inherited via a parent.
452 : For example INIT_VAL(foo.field) might inherit taintedness state from
453 : INIT_VAL(foo). */
454 11485210 : if (m_sm.inherited_state_p ())
455 3921491 : if (region_model_manager *mgr = ext_state.get_model_manager ())
456 : {
457 3921491 : if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
458 : {
459 252580 : const region *reg = init_sval->get_region ();
460 : /* Try recursing upwards (up to the base region for the
461 : cluster). */
462 252580 : if (!reg->base_region_p ())
463 60800 : if (const region *parent_reg = reg->get_parent_region ())
464 : {
465 60800 : const svalue *parent_init_sval
466 60800 : = mgr->get_or_create_initial_value (parent_reg);
467 60800 : state_machine::state_t parent_state
468 60800 : = get_state (parent_init_sval, ext_state);
469 60800 : if (parent_state)
470 : return parent_state;
471 : }
472 : }
473 3668911 : else if (const sub_svalue *sub_sval = sval->dyn_cast_sub_svalue ())
474 : {
475 20014 : const svalue *parent_sval = sub_sval->get_parent ();
476 40028 : if (state_machine::state_t parent_state
477 20014 : = get_state (parent_sval, ext_state))
478 : return parent_state;
479 : }
480 : }
481 :
482 22808792 : if (state_machine::state_t state
483 11404396 : = m_sm.alt_get_inherited_state (*this, sval, ext_state))
484 : return state;
485 :
486 11176054 : return m_sm.get_default_state (sval);
487 : }
488 :
489 : /* Get the "origin" svalue for any state of SVAL. */
490 :
491 : const svalue *
492 12 : sm_state_map::get_origin (const svalue *sval,
493 : const extrinsic_state &ext_state) const
494 : {
495 12 : gcc_assert (sval);
496 :
497 12 : sval = canonicalize_svalue (sval, ext_state);
498 :
499 12 : entry_t *slot
500 12 : = const_cast <map_t &> (m_map).get (sval);
501 12 : if (slot)
502 12 : return slot->m_origin;
503 : else
504 : return nullptr;
505 : }
506 :
507 : /* Set the state of SID within MODEL to STATE, recording that
508 : the state came from ORIGIN. */
509 :
510 : void
511 38147 : sm_state_map::set_state (region_model *model,
512 : const svalue *sval,
513 : state_machine::state_t state,
514 : const svalue *origin,
515 : const extrinsic_state &ext_state)
516 : {
517 38147 : if (model == nullptr)
518 : return;
519 :
520 : /* Reject attempts to set state on UNKNOWN/POISONED. */
521 38147 : if (!sval->can_have_associated_state_p ())
522 : return;
523 :
524 33433 : equiv_class &ec = model->get_constraints ()->get_equiv_class (sval);
525 33433 : if (!set_state (ec, state, origin, ext_state))
526 : return;
527 : }
528 :
529 : /* Set the state of EC to STATE, recording that the state came from
530 : ORIGIN.
531 : Return true if any states of svalue_ids within EC changed. */
532 :
533 : bool
534 33433 : sm_state_map::set_state (const equiv_class &ec,
535 : state_machine::state_t state,
536 : const svalue *origin,
537 : const extrinsic_state &ext_state)
538 : {
539 33433 : bool any_changed = false;
540 135508 : for (const svalue *sval : ec.m_vars)
541 35209 : any_changed |= impl_set_state (sval, state, origin, ext_state);
542 33433 : return any_changed;
543 : }
544 :
545 : /* Set state of SVAL to STATE, bypassing equivalence classes.
546 : Return true if the state changed. */
547 :
548 : bool
549 334048 : sm_state_map::impl_set_state (const svalue *sval,
550 : state_machine::state_t state,
551 : const svalue *origin,
552 : const extrinsic_state &ext_state)
553 : {
554 334048 : sval = canonicalize_svalue (sval, ext_state);
555 :
556 334048 : if (get_state (sval, ext_state) == state)
557 : return false;
558 :
559 264883 : gcc_assert (sval->can_have_associated_state_p ());
560 :
561 264883 : if (m_sm.inherited_state_p ())
562 : {
563 341336 : if (const compound_svalue *compound_sval
564 170668 : = sval->dyn_cast_compound_svalue ())
565 0 : for (auto iter = compound_sval->begin ();
566 0 : iter != compound_sval->end (); ++iter)
567 : {
568 0 : const svalue *inner_sval = iter->second;
569 0 : if (inner_sval->can_have_associated_state_p ())
570 0 : impl_set_state (inner_sval, state, origin, ext_state);
571 : }
572 : }
573 :
574 : /* Special-case state 0 as the default value. */
575 264883 : if (state == 0)
576 : {
577 987 : if (m_map.get (sval))
578 983 : m_map.remove (sval);
579 : return true;
580 : }
581 263896 : gcc_assert (sval);
582 263896 : m_map.put (sval, entry_t (state, origin));
583 263896 : return true;
584 : }
585 :
586 : /* Clear any state for SVAL from this state map. */
587 :
588 : void
589 3055 : sm_state_map::clear_any_state (const svalue *sval)
590 : {
591 3055 : m_map.remove (sval);
592 3055 : }
593 :
594 : /* Clear all per-svalue state within this state map. */
595 :
596 : void
597 9807 : sm_state_map::clear_all_per_svalue_state ()
598 : {
599 9807 : m_map.empty ();
600 9807 : }
601 :
602 : /* Set the "global" state within this state map to STATE. */
603 :
604 : void
605 297799 : sm_state_map::set_global_state (state_machine::state_t state)
606 : {
607 297799 : m_global_state = state;
608 297799 : }
609 :
610 : /* Get the "global" state within this state map. */
611 :
612 : state_machine::state_t
613 1400399 : sm_state_map::get_global_state () const
614 : {
615 1400399 : return m_global_state;
616 : }
617 :
618 : /* Purge any state for SVAL.
619 : If !SM::can_purge_p, then report the state as leaking,
620 : using CTXT. */
621 :
622 : void
623 677185 : sm_state_map::on_svalue_leak (const svalue *sval,
624 : impl_region_model_context *ctxt)
625 : {
626 677185 : if (state_machine::state_t state = get_state (sval, ctxt->m_ext_state))
627 : {
628 677185 : if (m_sm.can_purge_p (state))
629 676544 : m_map.remove (sval);
630 : else
631 641 : ctxt->on_state_leak (m_sm, sval, state);
632 : }
633 677185 : }
634 :
635 : /* Purge any state for svalues that aren't live with respect to LIVE_SVALUES
636 : and MODEL. */
637 :
638 : void
639 3668611 : sm_state_map::on_liveness_change (const svalue_set &live_svalues,
640 : const region_model *model,
641 : const extrinsic_state &ext_state,
642 : impl_region_model_context *ctxt)
643 : {
644 3668611 : svalue_set svals_to_unset;
645 3668611 : uncertainty_t *uncertainty = ctxt->get_uncertainty ();
646 :
647 3668611 : auto_vec<const svalue *> leaked_svals (m_map.elements ());
648 4585439 : for (map_t::iterator iter = m_map.begin ();
649 4585439 : iter != m_map.end ();
650 916828 : ++iter)
651 : {
652 916828 : const svalue *iter_sval = (*iter).first;
653 916828 : if (!iter_sval->live_p (&live_svalues, model))
654 : {
655 133781 : svals_to_unset.add (iter_sval);
656 133781 : entry_t e = (*iter).second;
657 133781 : if (!m_sm.can_purge_p (e.m_state))
658 984 : leaked_svals.quick_push (iter_sval);
659 : }
660 916828 : if (uncertainty)
661 838817 : if (uncertainty->unknown_sm_state_p (iter_sval))
662 308 : svals_to_unset.add (iter_sval);
663 : }
664 :
665 3668611 : leaked_svals.qsort (svalue::cmp_ptr_ptr);
666 :
667 3668611 : unsigned i;
668 3668611 : const svalue *sval;
669 4078607 : FOR_EACH_VEC_ELT (leaked_svals, i, sval)
670 : {
671 984 : entry_t e = *m_map.get (sval);
672 984 : ctxt->on_state_leak (m_sm, sval, e.m_state);
673 : }
674 :
675 3668611 : sm_state_map old_sm_map = *this;
676 :
677 3668611 : for (svalue_set::iterator iter = svals_to_unset.begin ();
678 3802700 : iter != svals_to_unset.end (); ++iter)
679 134089 : m_map.remove (*iter);
680 :
681 : /* For state machines like "taint" where states can be
682 : alt-inherited from other svalues, ensure that state purging doesn't
683 : make us lose sm-state.
684 :
685 : Consider e.g.:
686 :
687 : make_tainted(foo);
688 : if (foo.field > 128)
689 : return;
690 : arr[foo.field].f1 = v1;
691 :
692 : where the last line is:
693 :
694 : (A): _t1 = foo.field;
695 : (B): _t2 = _t1 * sizeof(arr[0]);
696 : (C): [arr + _t2].f1 = val;
697 :
698 : At (A), foo is 'tainted' and foo.field is 'has_ub'.
699 : After (B), foo.field's value (in _t1) is no longer directly
700 : within LIVE_SVALUES, so with state purging enabled, we would
701 : erroneously purge the "has_ub" state from the svalue.
702 :
703 : Given that _t2's value's state comes from _t1's value's state,
704 : we need to preserve that information.
705 :
706 : Hence for all svalues that have had their explicit sm-state unset,
707 : having their sm-state being unset, determine if doing so has changed
708 : their effective state, and if so, explicitly set their state.
709 :
710 : For example, in the above, unsetting the "has_ub" for _t1's value means
711 : that _t2's effective value changes from "has_ub" (from alt-inherited
712 : from _t1's value) to "tainted" (inherited from "foo"'s value).
713 :
714 : For such cases, preserve the effective state by explicitly setting the
715 : new state. In the above example, this means explicitly setting _t2's
716 : value to the value ("has_ub") it was previously alt-inheriting from _t1's
717 : value. */
718 3668611 : if (m_sm.has_alt_get_inherited_state_p ())
719 : {
720 524015 : auto_vec<const svalue *> svalues_needing_state;
721 655782 : for (auto unset_sval : svals_to_unset)
722 : {
723 131767 : const state_machine::state_t old_state
724 131767 : = old_sm_map.get_state (unset_sval, ext_state);
725 131767 : const state_machine::state_t new_state
726 131767 : = get_state (unset_sval, ext_state);
727 131767 : if (new_state != old_state)
728 131767 : svalues_needing_state.safe_push (unset_sval);
729 : }
730 773704 : for (auto sval : svalues_needing_state)
731 : {
732 131767 : const state_machine::state_t old_state
733 131767 : = old_sm_map.get_state (sval, ext_state);
734 131767 : impl_set_state (sval, old_state, nullptr, ext_state);
735 : }
736 524015 : }
737 3668611 : }
738 :
739 : /* Purge state from SVAL (in response to a call to an unknown function). */
740 :
741 : void
742 297968 : sm_state_map::on_unknown_change (const svalue *sval,
743 : bool is_mutable,
744 : const extrinsic_state &ext_state)
745 : {
746 297968 : svalue_set svals_to_unset;
747 :
748 320629 : for (map_t::iterator iter = m_map.begin ();
749 320629 : iter != m_map.end ();
750 22661 : ++iter)
751 : {
752 22661 : const svalue *key = (*iter).first;
753 22661 : entry_t e = (*iter).second;
754 : /* We only want to purge state for some states when things
755 : are mutable. For example, in sm-malloc.cc, an on-stack ptr
756 : doesn't stop being stack-allocated when passed to an unknown fn. */
757 22661 : if (!m_sm.reset_when_passed_to_unknown_fn_p (e.m_state, is_mutable))
758 10377 : continue;
759 12284 : if (key == sval)
760 857 : svals_to_unset.add (key);
761 : /* If we have INIT_VAL(BASE_REG), then unset any INIT_VAL(REG)
762 : for REG within BASE_REG. */
763 12284 : if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
764 2537 : if (const initial_svalue *init_key = key->dyn_cast_initial_svalue ())
765 : {
766 1161 : const region *changed_reg = init_sval->get_region ();
767 1161 : const region *changed_key = init_key->get_region ();
768 1161 : if (changed_key->get_base_region () == changed_reg)
769 182 : svals_to_unset.add (key);
770 : }
771 : }
772 :
773 298826 : for (svalue_set::iterator iter = svals_to_unset.begin ();
774 596794 : iter != svals_to_unset.end (); ++iter)
775 858 : impl_set_state (*iter, (state_machine::state_t)0, nullptr, ext_state);
776 297968 : }
777 :
778 : /* Purge state for things involving SVAL.
779 : For use when SVAL changes meaning, at the def_stmt on an SSA_NAME. */
780 :
781 : void
782 111251 : sm_state_map::purge_state_involving (const svalue *sval,
783 : const extrinsic_state &ext_state)
784 : {
785 : /* Currently svalue::involves_p requires this. */
786 222502 : if (!(sval->get_kind () == SK_INITIAL
787 111251 : || sval->get_kind () == SK_CONJURED))
788 0 : return;
789 :
790 111251 : svalue_set svals_to_unset;
791 :
792 135089 : for (map_t::iterator iter = m_map.begin ();
793 135089 : iter != m_map.end ();
794 23838 : ++iter)
795 : {
796 23838 : const svalue *key = (*iter).first;
797 23838 : entry_t e = (*iter).second;
798 23838 : if (!m_sm.can_purge_p (e.m_state))
799 9507 : continue;
800 14331 : if (key->involves_p (sval))
801 121 : svals_to_unset.add (key);
802 : }
803 :
804 111372 : for (svalue_set::iterator iter = svals_to_unset.begin ();
805 222623 : iter != svals_to_unset.end (); ++iter)
806 121 : impl_set_state (*iter, (state_machine::state_t)0, nullptr, ext_state);
807 111251 : }
808 :
809 : /* Comparator for imposing an order on sm_state_map instances. */
810 :
811 : int
812 1221096 : sm_state_map::cmp (const sm_state_map &smap_a, const sm_state_map &smap_b)
813 : {
814 1221096 : if (int cmp_count = smap_a.elements () - smap_b.elements ())
815 : return cmp_count;
816 :
817 1056372 : auto_vec <const svalue *> keys_a (smap_a.elements ());
818 1056372 : for (map_t::iterator iter = smap_a.begin ();
819 1760887 : iter != smap_a.end ();
820 704515 : ++iter)
821 704515 : keys_a.quick_push ((*iter).first);
822 1056372 : keys_a.qsort (svalue::cmp_ptr_ptr);
823 :
824 1056372 : auto_vec <const svalue *> keys_b (smap_b.elements ());
825 1056372 : for (map_t::iterator iter = smap_b.begin ();
826 1760887 : iter != smap_b.end ();
827 704515 : ++iter)
828 704515 : keys_b.quick_push ((*iter).first);
829 1056372 : keys_b.qsort (svalue::cmp_ptr_ptr);
830 :
831 1056372 : unsigned i;
832 1056372 : const svalue *sval_a;
833 2025646 : FOR_EACH_VEC_ELT (keys_a, i, sval_a)
834 : {
835 678643 : const svalue *sval_b = keys_b[i];
836 678643 : if (int cmp_sval = svalue::cmp_ptr (sval_a, sval_b))
837 25297 : return cmp_sval;
838 661734 : const entry_t *e_a = const_cast <map_t &> (smap_a.m_map).get (sval_a);
839 661734 : const entry_t *e_b = const_cast <map_t &> (smap_b.m_map).get (sval_b);
840 661734 : if (int cmp_entry = entry_t::cmp (*e_a, *e_b))
841 : return cmp_entry;
842 : }
843 :
844 : return 0;
845 1056372 : }
846 :
847 : /* Canonicalize SVAL before getting/setting it within the map.
848 : Convert all NULL pointers to (void *) to avoid state explosions
849 : involving all of the various (foo *)NULL vs (bar *)NULL. */
850 :
851 : const svalue *
852 12731294 : sm_state_map::canonicalize_svalue (const svalue *sval,
853 : const extrinsic_state &ext_state)
854 : {
855 12731294 : region_model_manager *mgr = ext_state.get_model_manager ();
856 12731294 : if (mgr && sval->get_type () && POINTER_TYPE_P (sval->get_type ()))
857 3413443 : if (tree cst = sval->maybe_get_constant ())
858 62433 : if (zerop (cst))
859 58755 : return mgr->get_or_create_constant_svalue (null_pointer_node);
860 :
861 : return sval;
862 : }
863 :
864 : /* Attempt to merge this state map with OTHER, writing the result
865 : into *OUT.
866 : Return true if the merger was possible, false otherwise.
867 :
868 : Normally, only identical state maps can be merged, so that
869 : differences between state maps lead to different enodes
870 :
871 : However some state machines may support merging states to
872 : allow for discarding of less important states, and thus avoid
873 : blow-up of the exploded graph. */
874 :
875 : bool
876 1631125 : sm_state_map::can_merge_with_p (const sm_state_map &other,
877 : const state_machine &sm,
878 : const extrinsic_state &ext_state,
879 : sm_state_map **out) const
880 : {
881 : /* If identical, then they merge trivially, with a copy. */
882 1631125 : if (*this == other)
883 : {
884 2758454 : delete *out;
885 1379227 : *out = clone ();
886 1379227 : return true;
887 : }
888 :
889 503796 : delete *out;
890 251898 : *out = new sm_state_map (sm);
891 :
892 : /* Otherwise, attempt to merge element by element. */
893 :
894 : /* Try to merge global state. */
895 503796 : if (state_machine::state_t merged_global_state
896 252758 : = sm.maybe_get_merged_state (get_global_state (),
897 : other.get_global_state ()))
898 251038 : (*out)->set_global_state (merged_global_state);
899 : else
900 : return false;
901 :
902 : /* Try to merge state each svalue's state (for the union
903 : of svalues represented by each smap).
904 : Ignore the origin information. */
905 251038 : hash_set<const svalue *> svals;
906 910900 : for (auto kv : *this)
907 659862 : svals.add (kv.first);
908 846882 : for (auto kv : other)
909 595844 : svals.add (kv.first);
910 417079 : for (auto sval : svals)
911 : {
912 365082 : state_machine::state_t this_state = get_state (sval, ext_state);
913 365082 : state_machine::state_t other_state = other.get_state (sval, ext_state);
914 365082 : if (state_machine::state_t merged_state
915 365082 : = sm.maybe_get_merged_state (this_state, other_state))
916 166041 : (*out)->impl_set_state (sval, merged_state, nullptr, ext_state);
917 : else
918 199041 : return false;
919 : }
920 :
921 : /* Successfully merged all elements. */
922 51997 : return true;
923 251038 : }
924 :
925 : /* class program_state. */
926 :
927 : /* program_state's ctor. */
928 :
929 363899 : program_state::program_state (const extrinsic_state &ext_state)
930 363899 : : m_region_model (nullptr),
931 363899 : m_checker_states (ext_state.get_num_checkers ()),
932 363899 : m_valid (true)
933 : {
934 363899 : engine *eng = ext_state.get_engine ();
935 363899 : region_model_manager *mgr = eng->get_model_manager ();
936 363899 : m_region_model = new region_model (mgr);
937 363899 : const int num_states = ext_state.get_num_checkers ();
938 2910689 : for (int i = 0; i < num_states; i++)
939 : {
940 2546790 : sm_state_map *sm = new sm_state_map (ext_state.get_sm (i));
941 2546790 : m_checker_states.quick_push (sm);
942 : }
943 363899 : }
944 :
945 : /* Attempt to use R to replay SUMMARY into this object.
946 : Return true if it is possible. */
947 :
948 : bool
949 9926 : sm_state_map::replay_call_summary (call_summary_replay &r,
950 : const sm_state_map &summary)
951 : {
952 12487 : for (auto kv : summary.m_map)
953 : {
954 2561 : const svalue *summary_sval = kv.first;
955 2561 : const svalue *caller_sval = r.convert_svalue_from_summary (summary_sval);
956 2561 : if (!caller_sval)
957 786 : continue;
958 2561 : if (!caller_sval->can_have_associated_state_p ())
959 786 : continue;
960 1775 : const svalue *summary_origin = kv.second.m_origin;
961 1775 : const svalue *caller_origin
962 : = (summary_origin
963 1775 : ? r.convert_svalue_from_summary (summary_origin)
964 : : nullptr);
965 : // caller_origin can be nullptr.
966 1775 : m_map.put (caller_sval, entry_t (kv.second.m_state, caller_origin));
967 : }
968 9926 : m_global_state = summary.m_global_state;
969 9926 : return true;
970 : }
971 :
972 : /* program_state's copy ctor. */
973 :
974 2023270 : program_state::program_state (const program_state &other)
975 2023270 : : m_region_model (new region_model (*other.m_region_model)),
976 4046540 : m_checker_states (other.m_checker_states.length ()),
977 2023270 : m_valid (true)
978 : {
979 2023270 : int i;
980 2023270 : sm_state_map *smap;
981 16174719 : FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
982 14151449 : m_checker_states.quick_push (smap->clone ());
983 2023270 : }
984 :
985 : /* program_state's assignment operator. */
986 :
987 : program_state&
988 10009 : program_state::operator= (const program_state &other)
989 : {
990 10009 : delete m_region_model;
991 10009 : m_region_model = new region_model (*other.m_region_model);
992 :
993 10009 : int i;
994 10009 : sm_state_map *smap;
995 79982 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
996 139946 : delete smap;
997 10009 : m_checker_states.truncate (0);
998 30027 : gcc_assert (m_checker_states.space (other.m_checker_states.length ()));
999 :
1000 79982 : FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
1001 69973 : m_checker_states.quick_push (smap->clone ());
1002 :
1003 10009 : m_valid = other.m_valid;
1004 :
1005 10009 : return *this;
1006 : }
1007 :
1008 : /* Move constructor for program_state (when building with C++11). */
1009 912743 : program_state::program_state (program_state &&other)
1010 912743 : : m_region_model (other.m_region_model),
1011 1825486 : m_checker_states (other.m_checker_states.length ())
1012 : {
1013 912743 : other.m_region_model = nullptr;
1014 :
1015 912743 : int i;
1016 912743 : sm_state_map *smap;
1017 8209229 : FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
1018 6383743 : m_checker_states.quick_push (smap);
1019 912743 : other.m_checker_states.truncate (0);
1020 :
1021 912743 : m_valid = other.m_valid;
1022 912743 : }
1023 :
1024 : /* Move assignment for program_state. */
1025 :
1026 : program_state&
1027 27702 : program_state::operator= (program_state &&other)
1028 : {
1029 27702 : if (this == &other)
1030 : return *this;
1031 :
1032 27702 : delete m_region_model;
1033 27702 : m_region_model = other.m_region_model;
1034 27702 : other.m_region_model = nullptr;
1035 :
1036 27702 : int i;
1037 27702 : sm_state_map *smap;
1038 249318 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1039 387828 : delete smap;
1040 27702 : m_checker_states.truncate (0);
1041 83106 : gcc_assert (m_checker_states.space (other.m_checker_states.length ()));
1042 249318 : FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
1043 193914 : m_checker_states.quick_push (smap);
1044 27702 : other.m_checker_states.truncate (0);
1045 :
1046 27702 : m_valid = other.m_valid;
1047 :
1048 27702 : return *this;
1049 : }
1050 :
1051 : /* program_state's dtor. */
1052 :
1053 3299912 : program_state::~program_state ()
1054 : {
1055 3299912 : delete m_region_model;
1056 3299912 : }
1057 :
1058 : /* Generate a hash value for this program_state. */
1059 :
1060 : hashval_t
1061 481353 : program_state::hash () const
1062 : {
1063 481353 : hashval_t result = m_region_model->hash ();
1064 :
1065 481353 : int i;
1066 481353 : sm_state_map *smap;
1067 4329430 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1068 3366724 : result ^= smap->hash ();
1069 481353 : return result;
1070 : }
1071 :
1072 : /* Equality operator for program_state.
1073 : All parts of the program_state (region model, checker states) must
1074 : equal their counterparts in OTHER for the two program_states to be
1075 : considered equal. */
1076 :
1077 : bool
1078 114060 : program_state::operator== (const program_state &other) const
1079 : {
1080 114060 : if (!(*m_region_model == *other.m_region_model))
1081 : return false;
1082 :
1083 : int i;
1084 : sm_state_map *smap;
1085 72520 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1086 63740 : if (!(*smap == *other.m_checker_states[i]))
1087 : return false;
1088 :
1089 8780 : gcc_checking_assert (hash () == other.hash ());
1090 :
1091 : return true;
1092 : }
1093 :
1094 : /* Print a compact representation of this state to PP. */
1095 :
1096 : void
1097 0 : program_state::print (const extrinsic_state &ext_state,
1098 : pretty_printer *pp) const
1099 : {
1100 0 : pp_printf (pp, "rmodel: ");
1101 0 : m_region_model->dump_to_pp (pp, true, false);
1102 0 : pp_newline (pp);
1103 :
1104 0 : int i;
1105 0 : sm_state_map *smap;
1106 0 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1107 : {
1108 0 : if (!smap->is_empty_p ())
1109 : {
1110 0 : pp_printf (pp, "%s: ", ext_state.get_name (i));
1111 0 : smap->print (m_region_model, true, false, pp);
1112 0 : pp_newline (pp);
1113 : }
1114 : }
1115 0 : if (!m_valid)
1116 : {
1117 0 : pp_printf (pp, "invalid state");
1118 0 : pp_newline (pp);
1119 : }
1120 0 : }
1121 :
1122 : /* Dump a representation of this state to PP. */
1123 :
1124 : void
1125 1748 : program_state::dump_to_pp (const extrinsic_state &ext_state,
1126 : bool /*summarize*/, bool multiline,
1127 : pretty_printer *pp) const
1128 : {
1129 1748 : if (!multiline)
1130 1355 : pp_string (pp, "{");
1131 1748 : {
1132 1748 : pp_printf (pp, "rmodel:");
1133 1748 : if (multiline)
1134 393 : pp_newline (pp);
1135 : else
1136 1355 : pp_string (pp, " {");
1137 1748 : m_region_model->dump_to_pp (pp, true, multiline);
1138 1748 : if (!multiline)
1139 1355 : pp_string (pp, "}");
1140 : }
1141 :
1142 1748 : int i;
1143 1748 : sm_state_map *smap;
1144 13984 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1145 : {
1146 12236 : if (!smap->is_empty_p ())
1147 : {
1148 413 : if (!multiline)
1149 101 : pp_string (pp, " {");
1150 413 : pp_printf (pp, "%s: ", ext_state.get_name (i));
1151 413 : if (multiline)
1152 312 : pp_newline (pp);
1153 413 : smap->print (m_region_model, true, multiline, pp);
1154 413 : if (!multiline)
1155 101 : pp_string (pp, "}");
1156 : }
1157 : }
1158 :
1159 1748 : if (!m_valid)
1160 : {
1161 0 : if (!multiline)
1162 0 : pp_space (pp);
1163 0 : pp_printf (pp, "invalid state");
1164 0 : if (multiline)
1165 0 : pp_newline (pp);
1166 : }
1167 1748 : if (!multiline)
1168 1355 : pp_string (pp, "}");
1169 1748 : }
1170 :
1171 : /* Dump a representation of this state to OUTF. */
1172 :
1173 : void
1174 0 : program_state::dump_to_file (const extrinsic_state &ext_state,
1175 : bool summarize, bool multiline,
1176 : FILE *outf) const
1177 : {
1178 0 : tree_dump_pretty_printer pp (outf);
1179 0 : dump_to_pp (ext_state, summarize, multiline, &pp);
1180 0 : }
1181 :
1182 : /* Dump a multiline representation of this state to stderr. */
1183 :
1184 : DEBUG_FUNCTION void
1185 0 : program_state::dump (const extrinsic_state &ext_state,
1186 : bool summarize) const
1187 : {
1188 0 : dump_to_file (ext_state, summarize, true, stderr);
1189 0 : }
1190 :
1191 : /* Dump a tree-like representation of this state to stderr. */
1192 :
1193 : DEBUG_FUNCTION void
1194 0 : program_state::dump () const
1195 : {
1196 0 : text_art::dump (*this);
1197 0 : }
1198 :
1199 : /* Return a new json::object of the form
1200 : {"store" : object for store,
1201 : "constraints" : object for constraint_manager,
1202 : "curr_frame" : (optional) str for current frame,
1203 : "checkers" : { STATE_NAME : object per sm_state_map },
1204 : "valid" : true/false}. */
1205 :
1206 : std::unique_ptr<json::object>
1207 0 : program_state::to_json (const extrinsic_state &ext_state) const
1208 : {
1209 0 : auto state_obj = std::make_unique<json::object> ();
1210 :
1211 0 : state_obj->set ("store", m_region_model->get_store ()->to_json ());
1212 0 : state_obj->set ("constraints",
1213 0 : m_region_model->get_constraints ()->to_json ());
1214 0 : if (m_region_model->get_current_frame ())
1215 0 : state_obj->set ("curr_frame",
1216 0 : m_region_model->get_current_frame ()->to_json ());
1217 :
1218 : /* Provide m_checker_states as an object, using names as keys. */
1219 0 : {
1220 0 : auto checkers_obj = std::make_unique<json::object> ();
1221 :
1222 0 : int i;
1223 0 : sm_state_map *smap;
1224 0 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1225 0 : if (!smap->is_empty_p ())
1226 0 : checkers_obj->set (ext_state.get_name (i), smap->to_json ());
1227 :
1228 0 : state_obj->set ("checkers", std::move (checkers_obj));
1229 0 : }
1230 :
1231 0 : state_obj->set_bool ("valid", m_valid);
1232 :
1233 0 : return state_obj;
1234 : }
1235 :
1236 :
1237 : std::unique_ptr<text_art::tree_widget>
1238 0 : program_state::make_dump_widget (const text_art::dump_widget_info &dwi) const
1239 : {
1240 0 : using text_art::tree_widget;
1241 0 : std::unique_ptr<tree_widget> state_widget
1242 0 : (tree_widget::from_fmt (dwi, nullptr, "State"));
1243 :
1244 0 : state_widget->add_child (m_region_model->make_dump_widget (dwi));
1245 :
1246 : /* Add nodes for any sm_state_maps with state. */
1247 0 : {
1248 0 : int i;
1249 0 : sm_state_map *smap;
1250 0 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1251 0 : if (!smap->is_empty_p ())
1252 0 : state_widget->add_child (smap->make_dump_widget (dwi, m_region_model));
1253 : }
1254 :
1255 0 : return state_widget;
1256 : }
1257 :
1258 : void
1259 0 : program_state::dump_dot (const extrinsic_state &ext_state) const
1260 : {
1261 0 : auto state_graph = make_diagnostic_state_graph (ext_state);
1262 :
1263 0 : gcc_assert (global_dc);
1264 0 : auto logical_loc_mgr = global_dc->get_logical_location_manager ();
1265 0 : gcc_assert (logical_loc_mgr);
1266 :
1267 0 : auto graph = diagnostics::state_graphs::make_dot_graph (*state_graph,
1268 0 : *logical_loc_mgr);
1269 :
1270 0 : pretty_printer pp;
1271 0 : dot::writer w (pp);
1272 0 : graph->print (w);
1273 0 : pp_flush (&pp);
1274 0 : }
1275 :
1276 : /* Update this program_state to reflect a top-level call to FUN.
1277 : The params will have initial_svalues. */
1278 :
1279 : void
1280 11137 : program_state::push_frame (const extrinsic_state &ext_state ATTRIBUTE_UNUSED,
1281 : const function &fun)
1282 : {
1283 11137 : m_region_model->push_frame (fun, nullptr, nullptr, nullptr);
1284 11137 : }
1285 :
1286 : /* Get the current function of this state. */
1287 :
1288 : const function *
1289 22 : program_state::get_current_function () const
1290 : {
1291 22 : return m_region_model->get_current_function ();
1292 : }
1293 :
1294 : /* Generate a simpler version of THIS, discarding state that's no longer
1295 : relevant at POINT.
1296 : The idea is that we're more likely to be able to consolidate
1297 : multiple (point, state) into single exploded_nodes if we discard
1298 : irrelevant state (e.g. at the end of functions). */
1299 :
1300 : program_state
1301 436091 : program_state::prune_for_point (exploded_graph &eg,
1302 : const program_point &point,
1303 : exploded_node *enode_for_diag,
1304 : uncertainty_t *uncertainty) const
1305 : {
1306 436091 : logger * const logger = eg.get_logger ();
1307 436091 : LOG_SCOPE (logger);
1308 :
1309 436091 : function *fun = point.get_function ();
1310 432588 : if (!fun)
1311 3503 : return *this;
1312 :
1313 432588 : program_state new_state (*this);
1314 :
1315 432588 : const state_purge_map *pm = eg.get_purge_map ();
1316 432588 : if (pm)
1317 : {
1318 432126 : unsigned num_ssas_purged = 0;
1319 432126 : unsigned num_decls_purged = 0;
1320 432126 : auto_vec<const decl_region *> regs;
1321 432126 : new_state.m_region_model->get_regions_for_current_frame (®s);
1322 432126 : regs.qsort (region::cmp_ptr_ptr);
1323 432126 : unsigned i;
1324 432126 : const decl_region *reg;
1325 2232797 : FOR_EACH_VEC_ELT (regs, i, reg)
1326 : {
1327 1800671 : const tree node = reg->get_decl ();
1328 1800671 : if (TREE_CODE (node) == SSA_NAME)
1329 : {
1330 1507297 : const tree ssa_name = node;
1331 1507297 : const state_purge_per_ssa_name &per_ssa
1332 1507297 : = pm->get_data_for_ssa_name (node);
1333 1507297 : if (!per_ssa.needed_at_supernode_p (point.get_supernode ()))
1334 : {
1335 : /* Don't purge bindings of SSA names to svalues
1336 : that have unpurgable sm-state, so that leaks are
1337 : reported at the end of the function, rather than
1338 : at the last place that such an SSA name is referred to.
1339 :
1340 : But do purge them for temporaries (when SSA_NAME_VAR is
1341 : NULL), so that we report for cases where a leak happens when
1342 : a variable is overwritten with another value, so that the leak
1343 : is reported at the point of overwrite, rather than having
1344 : temporaries keep the value reachable until the frame is
1345 : popped. */
1346 248372 : const svalue *sval
1347 248372 : = new_state.m_region_model->get_store_value (reg, nullptr);
1348 248372 : if (!new_state.can_purge_p (eg.get_ext_state (), sval)
1349 273919 : && SSA_NAME_VAR (ssa_name))
1350 : {
1351 : /* (currently only state maps can keep things
1352 : alive). */
1353 19330 : if (logger)
1354 0 : logger->log ("not purging binding for %qE"
1355 : " (used by state map)", ssa_name);
1356 19330 : continue;
1357 : }
1358 :
1359 229042 : new_state.m_region_model->purge_region (reg);
1360 229042 : num_ssas_purged++;
1361 : }
1362 : }
1363 : else
1364 : {
1365 293374 : const tree decl = node;
1366 293374 : gcc_assert (TREE_CODE (node) == VAR_DECL
1367 : || TREE_CODE (node) == PARM_DECL
1368 : || TREE_CODE (node) == RESULT_DECL);
1369 586748 : if (const state_purge_per_decl *per_decl
1370 293374 : = pm->get_any_data_for_decl (decl))
1371 267193 : if (!per_decl->needed_at_supernode_p (point.get_supernode ()))
1372 : {
1373 : /* Don't purge bindings of decls if there are svalues
1374 : that have unpurgable sm-state within the decl's cluster,
1375 : so that leaks are reported at the end of the function,
1376 : rather than at the last place that such a decl is
1377 : referred to. */
1378 3840 : if (!new_state.can_purge_base_region_p (eg.get_ext_state (),
1379 : reg))
1380 : {
1381 : /* (currently only state maps can keep things
1382 : alive). */
1383 1083 : if (logger)
1384 0 : logger->log ("not purging binding for %qE"
1385 : " (value in binding used by state map)",
1386 : decl);
1387 1083 : continue;
1388 : }
1389 :
1390 2757 : new_state.m_region_model->purge_region (reg);
1391 2757 : num_decls_purged++;
1392 : }
1393 : }
1394 : }
1395 :
1396 432126 : if (num_ssas_purged > 0 || num_decls_purged > 0)
1397 : {
1398 177758 : if (logger)
1399 : {
1400 108 : logger->log ("num_ssas_purged: %i", num_ssas_purged);
1401 108 : logger->log ("num_decl_purged: %i", num_decls_purged);
1402 : }
1403 177758 : impl_region_model_context ctxt (eg, enode_for_diag,
1404 : this,
1405 : &new_state,
1406 : uncertainty,
1407 177758 : nullptr);
1408 177758 : detect_leaks (*this, new_state, nullptr, eg.get_ext_state (), &ctxt);
1409 177758 : }
1410 432126 : }
1411 :
1412 432588 : new_state.m_region_model->canonicalize ();
1413 :
1414 432588 : return new_state;
1415 436091 : }
1416 :
1417 : /* Return true if there are no unpurgeable bindings within BASE_REG. */
1418 :
1419 : bool
1420 3840 : program_state::can_purge_base_region_p (const extrinsic_state &ext_state,
1421 : const region *base_reg) const
1422 : {
1423 3840 : binding_cluster *cluster
1424 3840 : = m_region_model->get_store ()->get_cluster (base_reg);
1425 3840 : if (!cluster)
1426 : return true;
1427 :
1428 13275 : for (auto iter : *cluster)
1429 : {
1430 6678 : const svalue *sval = iter.m_sval;
1431 6678 : if (!can_purge_p (ext_state, sval))
1432 1083 : return false;
1433 : }
1434 :
1435 2757 : return true;
1436 : }
1437 :
1438 : /* Get a representative tree to use for describing SVAL. */
1439 :
1440 : tree
1441 0 : program_state::get_representative_tree (const svalue *sval) const
1442 : {
1443 0 : gcc_assert (m_region_model);
1444 0 : return m_region_model->get_representative_tree (sval);
1445 : }
1446 :
1447 : /* Attempt to merge this state with OTHER, both at POINT.
1448 : Write the result to *OUT.
1449 : If the states were merged successfully, return true. */
1450 :
1451 : bool
1452 349229 : program_state::can_merge_with_p (const program_state &other,
1453 : const extrinsic_state &ext_state,
1454 : const program_point &point,
1455 : program_state *out) const
1456 : {
1457 349229 : gcc_assert (out);
1458 349229 : gcc_assert (m_region_model);
1459 :
1460 : /* Attempt to merge the sm-states. */
1461 : int i;
1462 : sm_state_map *smap;
1463 1780453 : FOR_EACH_VEC_ELT (out->m_checker_states, i, smap)
1464 3262250 : if (!m_checker_states[i]->can_merge_with_p (*other.m_checker_states[i],
1465 : ext_state.get_sm (i),
1466 : ext_state,
1467 1631125 : &out->m_checker_states[i]))
1468 : return false;
1469 :
1470 : /* Attempt to merge the region_models. */
1471 149328 : if (!m_region_model->can_merge_with_p (*other.m_region_model,
1472 : point,
1473 : out->m_region_model,
1474 : &ext_state,
1475 : this, &other))
1476 : return false;
1477 :
1478 40405 : out->m_region_model->canonicalize ();
1479 :
1480 40405 : return true;
1481 : }
1482 :
1483 : /* Assert that this object is valid. */
1484 :
1485 : void
1486 1876326 : program_state::validate (const extrinsic_state &ext_state) const
1487 : {
1488 : /* Skip this in a release build. */
1489 : #if !CHECKING_P
1490 : return;
1491 : #endif
1492 :
1493 3752652 : gcc_assert (m_checker_states.length () == ext_state.get_num_checkers ());
1494 1876326 : m_region_model->validate ();
1495 1876326 : }
1496 :
1497 : static void
1498 538 : log_set_of_svalues (logger *logger, const char *name,
1499 : const svalue_set &set)
1500 : {
1501 538 : logger->log ("%s", name);
1502 538 : logger->inc_indent ();
1503 538 : auto_vec<const svalue *> sval_vecs (set.elements ());
1504 538 : for (svalue_set::iterator iter = set.begin ();
1505 2655 : iter != set.end (); ++iter)
1506 2117 : sval_vecs.quick_push (*iter);
1507 538 : sval_vecs.qsort (svalue::cmp_ptr_ptr);
1508 538 : unsigned i;
1509 538 : const svalue *sval;
1510 2655 : FOR_EACH_VEC_ELT (sval_vecs, i, sval)
1511 : {
1512 2117 : logger->start_log_line ();
1513 2117 : pretty_printer *pp = logger->get_printer ();
1514 2117 : if (!flag_dump_noaddr)
1515 : {
1516 2117 : pp_pointer (pp, sval);
1517 2117 : pp_string (pp, ": ");
1518 : }
1519 2117 : sval->dump_to_pp (pp, false);
1520 2117 : logger->end_log_line ();
1521 : }
1522 538 : logger->dec_indent ();
1523 538 : }
1524 :
1525 : /* Compare the sets of svalues reachable from each of SRC_STATE and DEST_STATE.
1526 : For all svalues that are reachable in SRC_STATE and are not live in
1527 : DEST_STATE (whether explicitly reachable in DEST_STATE, or implicitly live
1528 : based on the former set), call CTXT->on_svalue_leak for them.
1529 :
1530 : Call on_liveness_change on both the CTXT and on the DEST_STATE's
1531 : constraint_manager, purging dead svalues from sm-state and from
1532 : constraints, respectively.
1533 :
1534 : This function should be called at each fine-grained state change, not
1535 : just at exploded edges. */
1536 :
1537 : void
1538 524396 : program_state::detect_leaks (const program_state &src_state,
1539 : const program_state &dest_state,
1540 : const svalue *extra_sval,
1541 : const extrinsic_state &ext_state,
1542 : region_model_context *ctxt)
1543 : {
1544 524396 : logger *logger = ext_state.get_logger ();
1545 524396 : LOG_SCOPE (logger);
1546 524396 : const uncertainty_t *uncertainty = ctxt->get_uncertainty ();
1547 524396 : if (logger)
1548 : {
1549 269 : pretty_printer *pp = logger->get_printer ();
1550 269 : logger->start_log_line ();
1551 269 : pp_string (pp, "src_state: ");
1552 269 : src_state.dump_to_pp (ext_state, true, false, pp);
1553 269 : logger->end_log_line ();
1554 269 : logger->start_log_line ();
1555 269 : pp_string (pp, "dest_state: ");
1556 269 : dest_state.dump_to_pp (ext_state, true, false, pp);
1557 269 : logger->end_log_line ();
1558 269 : if (extra_sval)
1559 : {
1560 1 : logger->start_log_line ();
1561 1 : pp_string (pp, "extra_sval: ");
1562 1 : extra_sval->dump_to_pp (pp, true);
1563 1 : logger->end_log_line ();
1564 : }
1565 269 : if (uncertainty)
1566 : {
1567 241 : logger->start_log_line ();
1568 241 : pp_string (pp, "uncertainty: ");
1569 241 : uncertainty->dump_to_pp (pp, true);
1570 241 : logger->end_log_line ();
1571 : }
1572 : }
1573 :
1574 : /* Get svalues reachable from each of src_state and dest_state.
1575 : Get svalues *known* to be reachable in src_state.
1576 : Pass in uncertainty for dest_state so that we additionally get svalues that
1577 : *might* still be reachable in dst_state. */
1578 524396 : svalue_set known_src_svalues;
1579 524396 : src_state.m_region_model->get_reachable_svalues (&known_src_svalues,
1580 : nullptr, nullptr);
1581 524396 : svalue_set maybe_dest_svalues;
1582 524396 : dest_state.m_region_model->get_reachable_svalues (&maybe_dest_svalues,
1583 : extra_sval, uncertainty);
1584 :
1585 524396 : if (logger)
1586 : {
1587 269 : log_set_of_svalues (logger, "src_state known reachable svalues:",
1588 : known_src_svalues);
1589 269 : log_set_of_svalues (logger, "dest_state maybe reachable svalues:",
1590 : maybe_dest_svalues);
1591 : }
1592 :
1593 524396 : auto_vec <const svalue *> dead_svals (known_src_svalues.elements ());
1594 5288608 : for (svalue_set::iterator iter = known_src_svalues.begin ();
1595 5288608 : iter != known_src_svalues.end (); ++iter)
1596 : {
1597 4764212 : const svalue *sval = (*iter);
1598 : /* For each sval reachable from SRC_STATE, determine if it is
1599 : live in DEST_STATE: either explicitly reachable, implicitly
1600 : live based on the set of explicitly reachable svalues,
1601 : or possibly reachable as recorded in uncertainty.
1602 : Record those that have ceased to be live i.e. were known
1603 : to be live, and are now not known to be even possibly-live. */
1604 4764212 : if (!sval->live_p (&maybe_dest_svalues, dest_state.m_region_model))
1605 96788 : dead_svals.quick_push (sval);
1606 : }
1607 :
1608 : /* Call CTXT->on_svalue_leak on all svals in SRC_STATE that have ceased
1609 : to be live, sorting them first to ensure deterministic behavior. */
1610 524396 : dead_svals.qsort (svalue::cmp_ptr_ptr);
1611 524396 : unsigned i;
1612 524396 : const svalue *sval;
1613 621184 : FOR_EACH_VEC_ELT (dead_svals, i, sval)
1614 96788 : ctxt->on_svalue_leak (sval);
1615 :
1616 : /* Purge dead svals from sm-state. */
1617 524396 : ctxt->on_liveness_change (maybe_dest_svalues,
1618 524396 : dest_state.m_region_model);
1619 :
1620 : /* Purge dead svals from constraints. */
1621 524396 : dest_state.m_region_model->get_constraints ()->on_liveness_change
1622 524396 : (maybe_dest_svalues, dest_state.m_region_model);
1623 :
1624 : /* Purge dead heap-allocated regions from dynamic extents. */
1625 1574464 : for (const svalue *sval : dead_svals)
1626 96788 : if (const region *reg = sval->maybe_get_region ())
1627 24984 : if (reg->get_kind () == RK_HEAP_ALLOCATED)
1628 6944 : dest_state.m_region_model->unset_dynamic_extents (reg);
1629 524396 : }
1630 :
1631 : /* Attempt to use R to replay SUMMARY into this object.
1632 : Return true if it is possible. */
1633 :
1634 : bool
1635 1541 : program_state::replay_call_summary (call_summary_replay &r,
1636 : const program_state &summary)
1637 : {
1638 1541 : if (!m_region_model->replay_call_summary (r, *summary.m_region_model))
1639 : return false;
1640 :
1641 11344 : for (unsigned sm_idx = 0; sm_idx < m_checker_states.length (); sm_idx++)
1642 : {
1643 9926 : const sm_state_map *summary_sm_map = summary.m_checker_states[sm_idx];
1644 9926 : m_checker_states[sm_idx]->replay_call_summary (r, *summary_sm_map);
1645 : }
1646 :
1647 1418 : if (!summary.m_valid)
1648 0 : m_valid = false;
1649 :
1650 : return true;
1651 : }
1652 :
1653 : /* Handle calls to "__analyzer_dump_state". */
1654 :
1655 : void
1656 357 : program_state::impl_call_analyzer_dump_state (const gcall &call,
1657 : const extrinsic_state &ext_state,
1658 : region_model_context *ctxt)
1659 : {
1660 357 : call_details cd (call, m_region_model, ctxt);
1661 357 : const char *sm_name = cd.get_arg_string_literal (0);
1662 357 : if (!sm_name)
1663 : {
1664 4 : error_at (call.location, "cannot determine state machine");
1665 12 : return;
1666 : }
1667 353 : unsigned sm_idx;
1668 353 : if (!ext_state.get_sm_idx_by_name (sm_name, &sm_idx))
1669 : {
1670 4 : error_at (call.location, "unrecognized state machine %qs", sm_name);
1671 4 : return;
1672 : }
1673 349 : const sm_state_map *smap = m_checker_states[sm_idx];
1674 :
1675 349 : const svalue *sval = cd.get_arg_svalue (1);
1676 :
1677 : /* Strip off cast to int (due to variadic args). */
1678 349 : if (const svalue *cast = sval->maybe_undo_cast ())
1679 5 : sval = cast;
1680 :
1681 349 : state_machine::state_t state = smap->get_state (sval, ext_state);
1682 349 : warning_at (call.location, 0, "state: %qs", state->get_name ());
1683 : }
1684 :
1685 : #if CHECKING_P
1686 :
1687 : namespace selftest {
1688 :
1689 : /* Tests for sm_state_map. */
1690 :
1691 : static void
1692 4 : test_sm_state_map ()
1693 : {
1694 4 : tree x = build_global_decl ("x", integer_type_node);
1695 4 : tree y = build_global_decl ("y", integer_type_node);
1696 4 : tree z = build_global_decl ("z", integer_type_node);
1697 :
1698 4 : std::unique_ptr<state_machine> sm = make_malloc_state_machine (nullptr);
1699 4 : state_machine::state_t start = sm->get_start_state ();
1700 4 : std::vector<std::unique_ptr<state_machine>> checkers;
1701 4 : const state_machine &borrowed_sm = *sm.get ();
1702 4 : checkers.push_back (std::move (sm));
1703 4 : region_model_manager mgr;
1704 4 : engine eng (mgr);
1705 4 : extrinsic_state ext_state (std::move (checkers), &eng);
1706 :
1707 : /* Test setting states on svalue_id instances directly. */
1708 4 : {
1709 4 : const state_machine::state test_state_42 ("test state 42", 42);
1710 4 : const state_machine::state_t TEST_STATE_42 = &test_state_42;
1711 4 : region_model model (&mgr);
1712 4 : const svalue *x_sval = model.get_rvalue (x, nullptr);
1713 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1714 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1715 :
1716 4 : sm_state_map map (borrowed_sm);
1717 4 : ASSERT_TRUE (map.is_empty_p ());
1718 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), start);
1719 :
1720 4 : map.impl_set_state (x_sval, TEST_STATE_42, z_sval, ext_state);
1721 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), TEST_STATE_42);
1722 4 : ASSERT_EQ (map.get_origin (x_sval, ext_state), z_sval);
1723 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), start);
1724 4 : ASSERT_FALSE (map.is_empty_p ());
1725 :
1726 4 : map.impl_set_state (y_sval, 0, z_sval, ext_state);
1727 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), start);
1728 :
1729 4 : map.impl_set_state (x_sval, 0, z_sval, ext_state);
1730 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), start);
1731 4 : ASSERT_TRUE (map.is_empty_p ());
1732 4 : }
1733 :
1734 4 : const state_machine::state test_state_5 ("test state 5", 5);
1735 4 : const state_machine::state_t TEST_STATE_5 = &test_state_5;
1736 :
1737 : /* Test setting states via equivalence classes. */
1738 4 : {
1739 4 : region_model model (&mgr);
1740 4 : const svalue *x_sval = model.get_rvalue (x, nullptr);
1741 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1742 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1743 :
1744 4 : sm_state_map map (borrowed_sm);
1745 4 : ASSERT_TRUE (map.is_empty_p ());
1746 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), start);
1747 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), start);
1748 :
1749 4 : model.add_constraint (x, EQ_EXPR, y, nullptr);
1750 :
1751 : /* Setting x to a state should also update y, as they
1752 : are in the same equivalence class. */
1753 4 : map.set_state (&model, x_sval, TEST_STATE_5, z_sval, ext_state);
1754 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), TEST_STATE_5);
1755 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), TEST_STATE_5);
1756 4 : ASSERT_EQ (map.get_origin (x_sval, ext_state), z_sval);
1757 4 : ASSERT_EQ (map.get_origin (y_sval, ext_state), z_sval);
1758 4 : }
1759 :
1760 : /* Test equality and hashing. */
1761 4 : {
1762 4 : region_model model (&mgr);
1763 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1764 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1765 :
1766 4 : sm_state_map map0 (borrowed_sm);
1767 4 : sm_state_map map1 (borrowed_sm);
1768 4 : sm_state_map map2 (borrowed_sm);
1769 :
1770 4 : ASSERT_EQ (map0.hash (), map1.hash ());
1771 4 : ASSERT_EQ (map0, map1);
1772 :
1773 4 : map1.impl_set_state (y_sval, TEST_STATE_5, z_sval, ext_state);
1774 4 : ASSERT_NE (map0.hash (), map1.hash ());
1775 4 : ASSERT_NE (map0, map1);
1776 :
1777 : /* Make the same change to map2. */
1778 4 : map2.impl_set_state (y_sval, TEST_STATE_5, z_sval, ext_state);
1779 4 : ASSERT_EQ (map1.hash (), map2.hash ());
1780 4 : ASSERT_EQ (map1, map2);
1781 4 : }
1782 :
1783 : /* Equality and hashing shouldn't depend on ordering. */
1784 4 : {
1785 4 : const state_machine::state test_state_2 ("test state 2", 2);
1786 4 : const state_machine::state_t TEST_STATE_2 = &test_state_2;
1787 4 : const state_machine::state test_state_3 ("test state 3", 3);
1788 4 : const state_machine::state_t TEST_STATE_3 = &test_state_3;
1789 4 : sm_state_map map0 (borrowed_sm);
1790 4 : sm_state_map map1 (borrowed_sm);
1791 4 : sm_state_map map2 (borrowed_sm);
1792 :
1793 4 : ASSERT_EQ (map0.hash (), map1.hash ());
1794 4 : ASSERT_EQ (map0, map1);
1795 :
1796 4 : region_model model (&mgr);
1797 4 : const svalue *x_sval = model.get_rvalue (x, nullptr);
1798 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1799 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1800 :
1801 4 : map1.impl_set_state (x_sval, TEST_STATE_2, nullptr, ext_state);
1802 4 : map1.impl_set_state (y_sval, TEST_STATE_3, nullptr, ext_state);
1803 4 : map1.impl_set_state (z_sval, TEST_STATE_2, nullptr, ext_state);
1804 :
1805 4 : map2.impl_set_state (z_sval, TEST_STATE_2, nullptr, ext_state);
1806 4 : map2.impl_set_state (y_sval, TEST_STATE_3, nullptr, ext_state);
1807 4 : map2.impl_set_state (x_sval, TEST_STATE_2, nullptr, ext_state);
1808 :
1809 4 : ASSERT_EQ (map1.hash (), map2.hash ());
1810 4 : ASSERT_EQ (map1, map2);
1811 4 : }
1812 :
1813 : // TODO: coverage for purging
1814 4 : }
1815 :
1816 : /* Check program_state works as expected. */
1817 :
1818 : static void
1819 4 : test_program_state_1 ()
1820 : {
1821 : /* Create a program_state for a global ptr "p" that has
1822 : malloc sm-state, pointing to a region on the heap. */
1823 4 : tree p = build_global_decl ("p", ptr_type_node);
1824 :
1825 4 : std::unique_ptr<state_machine> sm = make_malloc_state_machine (nullptr);
1826 4 : const state_machine::state_t UNCHECKED_STATE
1827 4 : = sm->get_state_by_name ("unchecked");
1828 :
1829 4 : region_model_manager mgr;
1830 4 : engine eng (mgr);
1831 4 : extrinsic_state ext_state (std::move (sm), &eng);
1832 4 : program_state s (ext_state);
1833 4 : region_model *model = s.m_region_model;
1834 4 : const svalue *size_in_bytes
1835 4 : = mgr.get_or_create_unknown_svalue (size_type_node);
1836 4 : const region *new_reg
1837 4 : = model->get_or_create_region_for_heap_alloc (size_in_bytes, nullptr);
1838 4 : const svalue *ptr_sval = mgr.get_ptr_svalue (ptr_type_node, new_reg);
1839 4 : model->set_value (model->get_lvalue (p, nullptr),
1840 : ptr_sval, nullptr);
1841 4 : sm_state_map *smap = s.m_checker_states[0];
1842 :
1843 4 : smap->impl_set_state (ptr_sval, UNCHECKED_STATE, nullptr, ext_state);
1844 4 : ASSERT_EQ (smap->get_state (ptr_sval, ext_state), UNCHECKED_STATE);
1845 4 : }
1846 :
1847 : /* Check that program_state works for string literals. */
1848 :
1849 : static void
1850 4 : test_program_state_2 ()
1851 : {
1852 : /* Create a program_state for a global ptr "p" that points to
1853 : a string constant. */
1854 4 : tree p = build_global_decl ("p", ptr_type_node);
1855 :
1856 4 : tree string_cst_ptr = build_string_literal (4, "foo");
1857 :
1858 4 : std::vector<std::unique_ptr<state_machine>> checkers;
1859 4 : region_model_manager mgr;
1860 4 : engine eng (mgr);
1861 4 : extrinsic_state ext_state (std::move (checkers), &eng);
1862 :
1863 4 : program_state s (ext_state);
1864 4 : region_model *model = s.m_region_model;
1865 4 : const region *p_reg = model->get_lvalue (p, nullptr);
1866 4 : const svalue *str_sval = model->get_rvalue (string_cst_ptr, nullptr);
1867 4 : model->set_value (p_reg, str_sval, nullptr);
1868 4 : }
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 :
1873 : static void
1874 4 : test_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 4 : tree p = build_global_decl ("p", ptr_type_node);
1879 :
1880 4 : region_model_manager mgr;
1881 4 : engine eng (mgr);
1882 4 : program_point point (program_point::origin (mgr));
1883 4 : extrinsic_state ext_state (make_malloc_state_machine (nullptr),
1884 4 : &eng);
1885 :
1886 4 : program_state s0 (ext_state);
1887 4 : uncertainty_t uncertainty;
1888 4 : impl_region_model_context ctxt (&s0, ext_state, &uncertainty);
1889 :
1890 4 : region_model *model0 = s0.m_region_model;
1891 4 : const svalue *size_in_bytes
1892 4 : = mgr.get_or_create_unknown_svalue (size_type_node);
1893 4 : const region *new_reg
1894 4 : = model0->get_or_create_region_for_heap_alloc (size_in_bytes, nullptr);
1895 4 : const svalue *ptr_sval = mgr.get_ptr_svalue (ptr_type_node, new_reg);
1896 4 : model0->set_value (model0->get_lvalue (p, &ctxt),
1897 : ptr_sval, &ctxt);
1898 4 : sm_state_map *smap = s0.m_checker_states[0];
1899 4 : const state_machine::state test_state ("test state", 0);
1900 4 : const state_machine::state_t TEST_STATE = &test_state;
1901 4 : smap->impl_set_state (ptr_sval, TEST_STATE, nullptr, ext_state);
1902 4 : ASSERT_EQ (smap->get_state (ptr_sval, ext_state), TEST_STATE);
1903 :
1904 4 : model0->canonicalize ();
1905 :
1906 : /* Verify that canonicalization preserves sm-state. */
1907 4 : ASSERT_EQ (smap->get_state (model0->get_rvalue (p, nullptr), ext_state),
1908 : TEST_STATE);
1909 :
1910 : /* Make a copy of the program_state. */
1911 4 : program_state s1 (s0);
1912 4 : ASSERT_EQ (s0, s1);
1913 :
1914 : /* We have two identical states with "p" pointing to a heap region
1915 : with the given sm-state.
1916 : They ought to be mergeable, preserving the sm-state. */
1917 4 : program_state merged (ext_state);
1918 4 : ASSERT_TRUE (s0.can_merge_with_p (s1, ext_state, point, &merged));
1919 4 : merged.validate (ext_state);
1920 :
1921 : /* Verify that the merged state has the sm-state for "p". */
1922 4 : region_model *merged_model = merged.m_region_model;
1923 4 : sm_state_map *merged_smap = merged.m_checker_states[0];
1924 4 : ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, nullptr),
1925 : ext_state),
1926 : TEST_STATE);
1927 :
1928 : /* Try canonicalizing. */
1929 4 : merged.m_region_model->canonicalize ();
1930 4 : merged.validate (ext_state);
1931 :
1932 : /* Verify that the merged state still has the sm-state for "p". */
1933 4 : ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, nullptr),
1934 : ext_state),
1935 : TEST_STATE);
1936 :
1937 : /* After canonicalization, we ought to have equality with the inputs. */
1938 4 : ASSERT_EQ (s0, merged);
1939 8 : }
1940 :
1941 : /* Verify that program_states with different global-state in an sm-state
1942 : can't be merged. */
1943 :
1944 : static void
1945 4 : test_program_state_merging_2 ()
1946 : {
1947 4 : region_model_manager mgr;
1948 4 : engine eng (mgr);
1949 4 : program_point point (program_point::origin (mgr));
1950 4 : extrinsic_state ext_state (make_signal_state_machine (nullptr), &eng);
1951 :
1952 4 : const state_machine::state test_state_0 ("test state 0", 0);
1953 4 : const state_machine::state test_state_1 ("test state 1", 1);
1954 4 : const state_machine::state_t TEST_STATE_0 = &test_state_0;
1955 4 : const state_machine::state_t TEST_STATE_1 = &test_state_1;
1956 :
1957 4 : program_state s0 (ext_state);
1958 4 : {
1959 4 : sm_state_map *smap0 = s0.m_checker_states[0];
1960 4 : smap0->set_global_state (TEST_STATE_0);
1961 4 : ASSERT_EQ (smap0->get_global_state (), TEST_STATE_0);
1962 : }
1963 :
1964 4 : program_state s1 (ext_state);
1965 4 : {
1966 4 : sm_state_map *smap1 = s1.m_checker_states[0];
1967 4 : smap1->set_global_state (TEST_STATE_1);
1968 4 : ASSERT_EQ (smap1->get_global_state (), TEST_STATE_1);
1969 : }
1970 :
1971 4 : ASSERT_NE (s0, s1);
1972 :
1973 : /* They ought to not be mergeable. */
1974 4 : program_state merged (ext_state);
1975 4 : ASSERT_FALSE (s0.can_merge_with_p (s1, ext_state, point, &merged));
1976 4 : }
1977 :
1978 : /* Run all of the selftests within this file. */
1979 :
1980 : void
1981 4 : analyzer_program_state_cc_tests ()
1982 : {
1983 4 : test_sm_state_map ();
1984 4 : test_program_state_1 ();
1985 4 : test_program_state_2 ();
1986 4 : test_program_state_merging ();
1987 4 : test_program_state_merging_2 ();
1988 4 : }
1989 :
1990 : } // namespace selftest
1991 :
1992 : #endif /* CHECKING_P */
1993 :
1994 : } // namespace ana
1995 :
1996 : #endif /* #if ENABLE_ANALYZER */
|
