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 16587253 : extrinsic_state::get_model_manager () const
114 : {
115 16587253 : if (m_engine)
116 16587253 : 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 722170 : extrinsic_state::get_sm_idx_by_name (const char *name, unsigned *out) const
127 : {
128 2885907 : for (size_t i = 0; i < m_checkers.size (); ++i)
129 2885436 : if (0 == strcmp (name, m_checkers[i]->get_name ()))
130 : {
131 : /* Found NAME. */
132 721699 : *out = i;
133 721699 : return true;
134 : }
135 :
136 : /* NAME not found. */
137 : return false;
138 : }
139 :
140 : /* struct sm_state_map::entry_t. */
141 :
142 : int
143 662196 : sm_state_map::entry_t::cmp (const entry_t &entry_a, const entry_t &entry_b)
144 : {
145 662196 : gcc_assert (entry_a.m_state);
146 662196 : gcc_assert (entry_b.m_state);
147 662196 : if (int cmp_state = ((int)entry_a.m_state->get_id ()
148 662196 : - (int)entry_b.m_state->get_id ()))
149 : return cmp_state;
150 653825 : if (entry_a.m_origin && entry_b.m_origin)
151 0 : return svalue::cmp_ptr (entry_a.m_origin, entry_b.m_origin);
152 653825 : if (entry_a.m_origin)
153 : return 1;
154 653825 : 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 2764166 : sm_state_map::sm_state_map (const state_machine &sm)
164 2764166 : : m_sm (sm), m_map (), m_global_state (sm.get_start_state ())
165 : {
166 2764166 : }
167 :
168 : /* Clone the sm_state_map. */
169 :
170 : sm_state_map *
171 17340663 : sm_state_map::clone () const
172 : {
173 17340663 : 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 : unsigned i;
205 : const svalue *sval;
206 1092 : 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 : unsigned i;
321 : 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 5953877 : sm_state_map::hash () const
383 : {
384 5953877 : 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 5953877 : for (map_t::iterator iter = m_map.begin ();
390 8255912 : iter != m_map.end ();
391 2302035 : ++iter)
392 : {
393 2302035 : inchash::hash hstate;
394 2302035 : hstate.add_ptr ((*iter).first);
395 2302035 : entry_t e = (*iter).second;
396 2302035 : hstate.add_int (e.m_state->get_id ());
397 2302035 : hstate.add_ptr (e.m_origin);
398 2302035 : result ^= hstate.end ();
399 : }
400 5953877 : result ^= m_global_state->get_id ();
401 :
402 5953877 : return result;
403 : }
404 :
405 : /* Equality operator for sm_state_map. */
406 :
407 : bool
408 1681429 : sm_state_map::operator== (const sm_state_map &other) const
409 : {
410 1681429 : if (m_global_state != other.m_global_state)
411 : return false;
412 :
413 1680398 : if (m_map.elements () != other.m_map.elements ())
414 : return false;
415 :
416 1456835 : for (map_t::iterator iter = m_map.begin ();
417 2281139 : iter != m_map.end ();
418 824304 : ++iter)
419 : {
420 850197 : const svalue *sval = (*iter).first;
421 850197 : entry_t e = (*iter).second;
422 850197 : entry_t *other_slot = const_cast <map_t &> (other.m_map).get (sval);
423 850197 : if (other_slot == nullptr)
424 25893 : return false;
425 1674501 : if (e != *other_slot)
426 : return false;
427 : }
428 :
429 1430942 : 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 12311716 : sm_state_map::get_state (const svalue *sval,
439 : const extrinsic_state &ext_state) const
440 : {
441 12311716 : gcc_assert (sval);
442 :
443 12311716 : sval = canonicalize_svalue (sval, ext_state);
444 :
445 24623432 : if (entry_t *slot
446 12311716 : = const_cast <map_t &> (m_map).get (sval))
447 982822 : 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 11328894 : if (m_sm.inherited_state_p ())
455 3890900 : if (region_model_manager *mgr = ext_state.get_model_manager ())
456 : {
457 3890900 : if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
458 : {
459 243913 : const region *reg = init_sval->get_region ();
460 : /* Try recursing upwards (up to the base region for the
461 : cluster). */
462 243913 : if (!reg->base_region_p ())
463 58439 : if (const region *parent_reg = reg->get_parent_region ())
464 : {
465 58439 : const svalue *parent_init_sval
466 58439 : = mgr->get_or_create_initial_value (parent_reg);
467 58439 : state_machine::state_t parent_state
468 58439 : = get_state (parent_init_sval, ext_state);
469 58439 : if (parent_state)
470 : return parent_state;
471 : }
472 : }
473 3646987 : else if (const sub_svalue *sub_sval = sval->dyn_cast_sub_svalue ())
474 : {
475 17993 : const svalue *parent_sval = sub_sval->get_parent ();
476 35986 : if (state_machine::state_t parent_state
477 17993 : = get_state (parent_sval, ext_state))
478 : return parent_state;
479 : }
480 : }
481 :
482 22504924 : if (state_machine::state_t state
483 11252462 : = m_sm.alt_get_inherited_state (*this, sval, ext_state))
484 : return state;
485 :
486 11035477 : 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 37236 : 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 37236 : if (model == nullptr)
518 : return;
519 :
520 : /* Reject attempts to set state on UNKNOWN/POISONED. */
521 37236 : if (!sval->can_have_associated_state_p ())
522 : return;
523 :
524 32663 : equiv_class &ec = model->get_constraints ()->get_equiv_class (sval);
525 32663 : 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 32663 : 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 32663 : bool any_changed = false;
540 132418 : for (const svalue *sval : ec.m_vars)
541 34429 : any_changed |= impl_set_state (sval, state, origin, ext_state);
542 32663 : 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 370993 : 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 370993 : sval = canonicalize_svalue (sval, ext_state);
555 :
556 370993 : if (get_state (sval, ext_state) == state)
557 : return false;
558 :
559 302838 : gcc_assert (sval->can_have_associated_state_p ());
560 :
561 302838 : if (m_sm.inherited_state_p ())
562 : {
563 427586 : if (const compound_svalue *compound_sval
564 213793 : = 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.get_svalue ();
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 302838 : if (state == 0)
576 : {
577 984 : if (m_map.get (sval))
578 980 : m_map.remove (sval);
579 984 : return true;
580 : }
581 301854 : gcc_assert (sval);
582 301854 : m_map.put (sval, entry_t (state, origin));
583 301854 : return true;
584 : }
585 :
586 : /* Clear any state for SVAL from this state map. */
587 :
588 : void
589 2910 : sm_state_map::clear_any_state (const svalue *sval)
590 : {
591 2910 : m_map.remove (sval);
592 2910 : }
593 :
594 : /* Clear all per-svalue state within this state map. */
595 :
596 : void
597 9681 : sm_state_map::clear_all_per_svalue_state ()
598 : {
599 9681 : m_map.empty ();
600 9681 : }
601 :
602 : /* Set the "global" state within this state map to STATE. */
603 :
604 : void
605 294009 : sm_state_map::set_global_state (state_machine::state_t state)
606 : {
607 294009 : m_global_state = state;
608 294009 : }
609 :
610 : /* Get the "global" state within this state map. */
611 :
612 : state_machine::state_t
613 1344074 : sm_state_map::get_global_state () const
614 : {
615 1344074 : 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 605120 : sm_state_map::on_svalue_leak (const svalue *sval,
624 : impl_region_model_context *ctxt)
625 : {
626 605120 : if (state_machine::state_t state = get_state (sval, ctxt->m_ext_state))
627 : {
628 605120 : if (m_sm.can_purge_p (state))
629 604486 : m_map.remove (sval);
630 : else
631 634 : ctxt->on_state_leak (m_sm, sval, state);
632 : }
633 605120 : }
634 :
635 : /* Purge any state for svalues that aren't live with respect to LIVE_SVALUES
636 : and MODEL. */
637 :
638 : void
639 3386574 : 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 3386574 : svalue_set svals_to_unset;
645 3386574 : uncertainty_t *uncertainty = ctxt->get_uncertainty ();
646 :
647 3386574 : auto_vec<const svalue *> leaked_svals (m_map.elements ());
648 4294736 : for (map_t::iterator iter = m_map.begin ();
649 4294736 : iter != m_map.end ();
650 908162 : ++iter)
651 : {
652 908162 : const svalue *iter_sval = (*iter).first;
653 908162 : if (!iter_sval->live_p (&live_svalues, model))
654 : {
655 133677 : svals_to_unset.add (iter_sval);
656 133677 : entry_t e = (*iter).second;
657 133677 : if (!m_sm.can_purge_p (e.m_state))
658 937 : leaked_svals.quick_push (iter_sval);
659 : }
660 908162 : if (uncertainty)
661 830824 : if (uncertainty->unknown_sm_state_p (iter_sval))
662 308 : svals_to_unset.add (iter_sval);
663 : }
664 :
665 3386574 : leaked_svals.qsort (svalue::cmp_ptr_ptr);
666 :
667 : unsigned i;
668 : const svalue *sval;
669 3387511 : FOR_EACH_VEC_ELT (leaked_svals, i, sval)
670 : {
671 937 : entry_t e = *m_map.get (sval);
672 937 : ctxt->on_state_leak (m_sm, sval, e.m_state);
673 : }
674 :
675 3386574 : sm_state_map old_sm_map = *this;
676 :
677 3386574 : for (svalue_set::iterator iter = svals_to_unset.begin ();
678 3654544 : iter != svals_to_unset.end (); ++iter)
679 133985 : 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 3386574 : if (m_sm.has_alt_get_inherited_state_p ())
719 : {
720 483724 : auto_vec<const svalue *> svalues_needing_state;
721 747258 : 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 733413 : 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 483724 : }
737 3386574 : }
738 :
739 : /* Purge state from SVAL (in response to a call to an unknown function). */
740 :
741 : void
742 295637 : sm_state_map::on_unknown_change (const svalue *sval,
743 : bool is_mutable,
744 : const extrinsic_state &ext_state)
745 : {
746 295637 : svalue_set svals_to_unset;
747 :
748 318408 : for (map_t::iterator iter = m_map.begin ();
749 318408 : iter != m_map.end ();
750 22771 : ++iter)
751 : {
752 22771 : const svalue *key = (*iter).first;
753 22771 : 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 22771 : if (!m_sm.reset_when_passed_to_unknown_fn_p (e.m_state, is_mutable))
758 10378 : continue;
759 12393 : if (key == sval)
760 854 : 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 12393 : if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
764 2517 : if (const initial_svalue *init_key = key->dyn_cast_initial_svalue ())
765 : {
766 1174 : const region *changed_reg = init_sval->get_region ();
767 1174 : const region *changed_key = init_key->get_region ();
768 1174 : if (changed_key->get_base_region () == changed_reg)
769 182 : svals_to_unset.add (key);
770 : }
771 : }
772 :
773 296492 : for (svalue_set::iterator iter = svals_to_unset.begin ();
774 592984 : iter != svals_to_unset.end (); ++iter)
775 855 : impl_set_state (*iter, (state_machine::state_t)0, nullptr, ext_state);
776 295637 : }
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 110124 : sm_state_map::purge_state_involving (const svalue *sval,
783 : const extrinsic_state &ext_state)
784 : {
785 : /* Currently svalue::involves_p requires this. */
786 220248 : if (!(sval->get_kind () == SK_INITIAL
787 110124 : || sval->get_kind () == SK_CONJURED))
788 0 : return;
789 :
790 110124 : svalue_set svals_to_unset;
791 :
792 133933 : for (map_t::iterator iter = m_map.begin ();
793 133933 : iter != m_map.end ();
794 23809 : ++iter)
795 : {
796 23809 : const svalue *key = (*iter).first;
797 23809 : entry_t e = (*iter).second;
798 23809 : if (!m_sm.can_purge_p (e.m_state))
799 9538 : continue;
800 14271 : if (key->involves_p (sval))
801 121 : svals_to_unset.add (key);
802 : }
803 :
804 110245 : for (svalue_set::iterator iter = svals_to_unset.begin ();
805 220490 : iter != svals_to_unset.end (); ++iter)
806 121 : impl_set_state (*iter, (state_machine::state_t)0, nullptr, ext_state);
807 110124 : }
808 :
809 : /* Comparator for imposing an order on sm_state_map instances. */
810 :
811 : int
812 1206040 : sm_state_map::cmp (const sm_state_map &smap_a, const sm_state_map &smap_b)
813 : {
814 1206040 : if (int cmp_count = smap_a.elements () - smap_b.elements ())
815 : return cmp_count;
816 :
817 1043298 : auto_vec <const svalue *> keys_a (smap_a.elements ());
818 1043298 : for (map_t::iterator iter = smap_a.begin ();
819 1748159 : iter != smap_a.end ();
820 704861 : ++iter)
821 704861 : keys_a.quick_push ((*iter).first);
822 1043298 : keys_a.qsort (svalue::cmp_ptr_ptr);
823 :
824 1043298 : auto_vec <const svalue *> keys_b (smap_b.elements ());
825 1043298 : for (map_t::iterator iter = smap_b.begin ();
826 1748159 : iter != smap_b.end ();
827 704861 : ++iter)
828 704861 : keys_b.quick_push ((*iter).first);
829 1043298 : keys_b.qsort (svalue::cmp_ptr_ptr);
830 :
831 : unsigned i;
832 : const svalue *sval_a;
833 2013108 : FOR_EACH_VEC_ELT (keys_a, i, sval_a)
834 : {
835 679001 : const svalue *sval_b = keys_b[i];
836 679001 : if (int cmp_sval = svalue::cmp_ptr (sval_a, sval_b))
837 25176 : return cmp_sval;
838 662196 : const entry_t *e_a = const_cast <map_t &> (smap_a.m_map).get (sval_a);
839 662196 : const entry_t *e_b = const_cast <map_t &> (smap_b.m_map).get (sval_b);
840 662196 : if (int cmp_entry = entry_t::cmp (*e_a, *e_b))
841 : return cmp_entry;
842 : }
843 :
844 : return 0;
845 1043298 : }
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 12682721 : sm_state_map::canonicalize_svalue (const svalue *sval,
853 : const extrinsic_state &ext_state)
854 : {
855 12682721 : region_model_manager *mgr = ext_state.get_model_manager ();
856 12682721 : if (mgr && sval->get_type () && POINTER_TYPE_P (sval->get_type ()))
857 3435775 : if (tree cst = sval->maybe_get_constant ())
858 58954 : if (zerop (cst))
859 56268 : 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 1618167 : 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 1618167 : if (*this == other)
883 : {
884 2737344 : delete *out;
885 1368672 : *out = clone ();
886 1368672 : return true;
887 : }
888 :
889 498990 : delete *out;
890 249495 : *out = new sm_state_map (sm);
891 :
892 : /* Otherwise, attempt to merge element by element. */
893 :
894 : /* Try to merge global state. */
895 498990 : if (state_machine::state_t merged_global_state
896 250355 : = sm.maybe_get_merged_state (get_global_state (),
897 : other.get_global_state ()))
898 248635 : (*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 248635 : hash_set<const svalue *> svals;
906 907229 : for (auto kv : *this)
907 658594 : svals.add (kv.first);
908 843089 : for (auto kv : other)
909 594454 : svals.add (kv.first);
910 656173 : for (auto sval : svals)
911 : {
912 400987 : state_machine::state_t this_state = get_state (sval, ext_state);
913 400987 : state_machine::state_t other_state = other.get_state (sval, ext_state);
914 400987 : if (state_machine::state_t merged_state
915 400987 : = sm.maybe_get_merged_state (this_state, other_state))
916 203769 : (*out)->impl_set_state (sval, merged_state, nullptr, ext_state);
917 : else
918 197218 : return false;
919 : }
920 :
921 : /* Successfully merged all elements. */
922 51417 : return true;
923 248635 : }
924 :
925 : /* class program_state. */
926 :
927 : /* program_state's ctor. */
928 :
929 359306 : program_state::program_state (const extrinsic_state &ext_state)
930 359306 : : m_region_model (nullptr),
931 359306 : m_checker_states (ext_state.get_num_checkers ()),
932 359306 : m_valid (true)
933 : {
934 359306 : engine *eng = ext_state.get_engine ();
935 359306 : region_model_manager *mgr = eng->get_model_manager ();
936 359306 : m_region_model = new region_model (mgr);
937 359306 : const int num_states = ext_state.get_num_checkers ();
938 2873945 : for (int i = 0; i < num_states; i++)
939 : {
940 2514639 : sm_state_map *sm = new sm_state_map (ext_state.get_sm (i));
941 2514639 : m_checker_states.quick_push (sm);
942 : }
943 359306 : }
944 :
945 : /* Attempt to use R to replay SUMMARY into this object.
946 : Return true if it is possible. */
947 :
948 : bool
949 9919 : sm_state_map::replay_call_summary (call_summary_replay &r,
950 : const sm_state_map &summary)
951 : {
952 14991 : for (auto kv : summary.m_map)
953 : {
954 2536 : const svalue *summary_sval = kv.first;
955 2536 : const svalue *caller_sval = r.convert_svalue_from_summary (summary_sval);
956 2536 : if (!caller_sval)
957 768 : continue;
958 2536 : if (!caller_sval->can_have_associated_state_p ())
959 768 : continue;
960 1768 : const svalue *summary_origin = kv.second.m_origin;
961 1768 : const svalue *caller_origin
962 : = (summary_origin
963 1768 : ? r.convert_svalue_from_summary (summary_origin)
964 : : nullptr);
965 : // caller_origin can be nullptr.
966 1768 : m_map.put (caller_sval, entry_t (kv.second.m_state, caller_origin));
967 : }
968 9919 : m_global_state = summary.m_global_state;
969 9919 : return true;
970 : }
971 :
972 : /* program_state's copy ctor. */
973 :
974 2246392 : program_state::program_state (const program_state &other)
975 2246392 : : m_region_model (new region_model (*other.m_region_model)),
976 4492784 : m_checker_states (other.m_checker_states.length ()),
977 2246392 : m_valid (true)
978 : {
979 2246392 : int i;
980 2246392 : sm_state_map *smap;
981 17957044 : FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
982 15710652 : m_checker_states.quick_push (smap->clone ());
983 2246392 : }
984 :
985 : /* program_state's assignment operator. */
986 :
987 : program_state&
988 37347 : program_state::operator= (const program_state &other)
989 : {
990 37347 : delete m_region_model;
991 37347 : m_region_model = new region_model (*other.m_region_model);
992 :
993 37347 : int i;
994 37347 : sm_state_map *smap;
995 298686 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
996 522678 : delete smap;
997 37347 : m_checker_states.truncate (0);
998 112041 : gcc_assert (m_checker_states.space (other.m_checker_states.length ()));
999 :
1000 298686 : FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
1001 261339 : m_checker_states.quick_push (smap->clone ());
1002 :
1003 37347 : m_valid = other.m_valid;
1004 :
1005 37347 : return *this;
1006 : }
1007 :
1008 : /* Move constructor for program_state (when building with C++11). */
1009 443447 : program_state::program_state (program_state &&other)
1010 443447 : : m_region_model (other.m_region_model),
1011 886894 : m_checker_states (other.m_checker_states.length ())
1012 : {
1013 443447 : other.m_region_model = nullptr;
1014 :
1015 443447 : int i;
1016 443447 : sm_state_map *smap;
1017 3544769 : FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
1018 3101322 : m_checker_states.quick_push (smap);
1019 443447 : other.m_checker_states.truncate (0);
1020 :
1021 443447 : m_valid = other.m_valid;
1022 443447 : }
1023 :
1024 : /* program_state's dtor. */
1025 :
1026 3049145 : program_state::~program_state ()
1027 : {
1028 3049145 : delete m_region_model;
1029 3049145 : }
1030 :
1031 : /* Generate a hash value for this program_state. */
1032 :
1033 : hashval_t
1034 442100 : program_state::hash () const
1035 : {
1036 442100 : hashval_t result = m_region_model->hash ();
1037 :
1038 442100 : int i;
1039 442100 : sm_state_map *smap;
1040 3976153 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1041 3091953 : result ^= smap->hash ();
1042 442100 : return result;
1043 : }
1044 :
1045 : /* Equality operator for program_state.
1046 : All parts of the program_state (region model, checker states) must
1047 : equal their counterparts in OTHER for the two program_states to be
1048 : considered equal. */
1049 :
1050 : bool
1051 112392 : program_state::operator== (const program_state &other) const
1052 : {
1053 112392 : if (!(*m_region_model == *other.m_region_model))
1054 : return false;
1055 :
1056 : int i;
1057 : sm_state_map *smap;
1058 71956 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1059 63242 : if (!(*smap == *other.m_checker_states[i]))
1060 : return false;
1061 :
1062 8714 : gcc_checking_assert (hash () == other.hash ());
1063 :
1064 : return true;
1065 : }
1066 :
1067 : /* Print a compact representation of this state to PP. */
1068 :
1069 : void
1070 0 : program_state::print (const extrinsic_state &ext_state,
1071 : pretty_printer *pp) const
1072 : {
1073 0 : pp_printf (pp, "rmodel: ");
1074 0 : m_region_model->dump_to_pp (pp, true, false);
1075 0 : pp_newline (pp);
1076 :
1077 0 : int i;
1078 0 : sm_state_map *smap;
1079 0 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1080 : {
1081 0 : if (!smap->is_empty_p ())
1082 : {
1083 0 : pp_printf (pp, "%s: ", ext_state.get_name (i));
1084 0 : smap->print (m_region_model, true, false, pp);
1085 0 : pp_newline (pp);
1086 : }
1087 : }
1088 0 : if (!m_valid)
1089 : {
1090 0 : pp_printf (pp, "invalid state");
1091 0 : pp_newline (pp);
1092 : }
1093 0 : }
1094 :
1095 : /* Dump a representation of this state to PP. */
1096 :
1097 : void
1098 1748 : program_state::dump_to_pp (const extrinsic_state &ext_state,
1099 : bool /*summarize*/, bool multiline,
1100 : pretty_printer *pp) const
1101 : {
1102 1748 : if (!multiline)
1103 1355 : pp_string (pp, "{");
1104 1748 : {
1105 1748 : pp_printf (pp, "rmodel:");
1106 1748 : if (multiline)
1107 393 : pp_newline (pp);
1108 : else
1109 1355 : pp_string (pp, " {");
1110 1748 : m_region_model->dump_to_pp (pp, true, multiline);
1111 1748 : if (!multiline)
1112 1355 : pp_string (pp, "}");
1113 : }
1114 :
1115 : int i;
1116 : sm_state_map *smap;
1117 13984 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1118 : {
1119 12236 : if (!smap->is_empty_p ())
1120 : {
1121 413 : if (!multiline)
1122 101 : pp_string (pp, " {");
1123 413 : pp_printf (pp, "%s: ", ext_state.get_name (i));
1124 413 : if (multiline)
1125 312 : pp_newline (pp);
1126 413 : smap->print (m_region_model, true, multiline, pp);
1127 413 : if (!multiline)
1128 101 : pp_string (pp, "}");
1129 : }
1130 : }
1131 :
1132 1748 : if (!m_valid)
1133 : {
1134 0 : if (!multiline)
1135 0 : pp_space (pp);
1136 0 : pp_printf (pp, "invalid state");
1137 0 : if (multiline)
1138 0 : pp_newline (pp);
1139 : }
1140 1748 : if (!multiline)
1141 1355 : pp_string (pp, "}");
1142 1748 : }
1143 :
1144 : /* Dump a representation of this state to OUTF. */
1145 :
1146 : void
1147 0 : program_state::dump_to_file (const extrinsic_state &ext_state,
1148 : bool summarize, bool multiline,
1149 : FILE *outf) const
1150 : {
1151 0 : tree_dump_pretty_printer pp (outf);
1152 0 : dump_to_pp (ext_state, summarize, multiline, &pp);
1153 0 : }
1154 :
1155 : /* Dump a multiline representation of this state to stderr. */
1156 :
1157 : DEBUG_FUNCTION void
1158 0 : program_state::dump (const extrinsic_state &ext_state,
1159 : bool summarize) const
1160 : {
1161 0 : dump_to_file (ext_state, summarize, true, stderr);
1162 0 : }
1163 :
1164 : /* Dump a tree-like representation of this state to stderr. */
1165 :
1166 : DEBUG_FUNCTION void
1167 0 : program_state::dump () const
1168 : {
1169 0 : text_art::dump (*this);
1170 0 : }
1171 :
1172 : /* Return a new json::object of the form
1173 : {"store" : object for store,
1174 : "constraints" : object for constraint_manager,
1175 : "curr_frame" : (optional) str for current frame,
1176 : "checkers" : { STATE_NAME : object per sm_state_map },
1177 : "valid" : true/false}. */
1178 :
1179 : std::unique_ptr<json::object>
1180 0 : program_state::to_json (const extrinsic_state &ext_state) const
1181 : {
1182 0 : auto state_obj = std::make_unique<json::object> ();
1183 :
1184 0 : state_obj->set ("store", m_region_model->get_store ()->to_json ());
1185 0 : state_obj->set ("constraints",
1186 0 : m_region_model->get_constraints ()->to_json ());
1187 0 : if (m_region_model->get_current_frame ())
1188 0 : state_obj->set ("curr_frame",
1189 0 : m_region_model->get_current_frame ()->to_json ());
1190 :
1191 : /* Provide m_checker_states as an object, using names as keys. */
1192 0 : {
1193 0 : auto checkers_obj = std::make_unique<json::object> ();
1194 :
1195 0 : int i;
1196 0 : sm_state_map *smap;
1197 0 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1198 0 : if (!smap->is_empty_p ())
1199 0 : checkers_obj->set (ext_state.get_name (i), smap->to_json ());
1200 :
1201 0 : state_obj->set ("checkers", std::move (checkers_obj));
1202 0 : }
1203 :
1204 0 : state_obj->set_bool ("valid", m_valid);
1205 :
1206 0 : return state_obj;
1207 : }
1208 :
1209 :
1210 : std::unique_ptr<text_art::tree_widget>
1211 0 : program_state::make_dump_widget (const text_art::dump_widget_info &dwi) const
1212 : {
1213 0 : using text_art::tree_widget;
1214 0 : std::unique_ptr<tree_widget> state_widget
1215 0 : (tree_widget::from_fmt (dwi, nullptr, "State"));
1216 :
1217 0 : state_widget->add_child (m_region_model->make_dump_widget (dwi));
1218 :
1219 : /* Add nodes for any sm_state_maps with state. */
1220 0 : {
1221 0 : int i;
1222 0 : sm_state_map *smap;
1223 0 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1224 0 : if (!smap->is_empty_p ())
1225 0 : state_widget->add_child (smap->make_dump_widget (dwi, m_region_model));
1226 : }
1227 :
1228 0 : return state_widget;
1229 : }
1230 :
1231 : void
1232 0 : program_state::dump_dot (const extrinsic_state &ext_state) const
1233 : {
1234 0 : auto state_graph = make_diagnostic_state_graph (ext_state);
1235 :
1236 0 : gcc_assert (global_dc);
1237 0 : auto logical_loc_mgr = global_dc->get_logical_location_manager ();
1238 0 : gcc_assert (logical_loc_mgr);
1239 :
1240 0 : auto graph = diagnostics::state_graphs::make_dot_graph (*state_graph,
1241 0 : *logical_loc_mgr);
1242 :
1243 0 : pretty_printer pp;
1244 0 : dot::writer w (pp);
1245 0 : graph->print (w);
1246 0 : pp_flush (&pp);
1247 0 : }
1248 :
1249 : /* Update this program_state to reflect a top-level call to FUN.
1250 : The params will have initial_svalues. */
1251 :
1252 : void
1253 10061 : program_state::push_frame (const extrinsic_state &ext_state ATTRIBUTE_UNUSED,
1254 : const function &fun)
1255 : {
1256 10061 : m_region_model->push_frame (fun, nullptr, nullptr, nullptr);
1257 10061 : }
1258 :
1259 : /* Get the current function of this state. */
1260 :
1261 : const function *
1262 22 : program_state::get_current_function () const
1263 : {
1264 22 : return m_region_model->get_current_function ();
1265 : }
1266 :
1267 : /* Generate a simpler version of THIS, discarding state that's no longer
1268 : relevant at POINT.
1269 : The idea is that we're more likely to be able to consolidate
1270 : multiple (point, state) into single exploded_nodes if we discard
1271 : irrelevant state (e.g. at the end of functions). */
1272 :
1273 : program_state
1274 397148 : program_state::prune_for_point (exploded_graph &eg,
1275 : const program_point &point,
1276 : exploded_node *enode_for_diag,
1277 : uncertainty_t *uncertainty) const
1278 : {
1279 397148 : logger * const logger = eg.get_logger ();
1280 397148 : LOG_SCOPE (logger);
1281 :
1282 397148 : function *fun = point.get_function ();
1283 393771 : if (!fun)
1284 3377 : return *this;
1285 :
1286 393771 : program_state new_state (*this);
1287 :
1288 393771 : const state_purge_map *pm = eg.get_purge_map ();
1289 393771 : if (pm)
1290 : {
1291 393393 : unsigned num_ssas_purged = 0;
1292 393393 : unsigned num_decls_purged = 0;
1293 393393 : auto_vec<const decl_region *> regs;
1294 393393 : new_state.m_region_model->get_regions_for_current_frame (®s);
1295 393393 : regs.qsort (region::cmp_ptr_ptr);
1296 : unsigned i;
1297 : const decl_region *reg;
1298 2134788 : FOR_EACH_VEC_ELT (regs, i, reg)
1299 : {
1300 1741395 : const tree node = reg->get_decl ();
1301 1741395 : if (TREE_CODE (node) == SSA_NAME)
1302 : {
1303 1456987 : const tree ssa_name = node;
1304 1456987 : const state_purge_per_ssa_name &per_ssa
1305 1456987 : = pm->get_data_for_ssa_name (node);
1306 1456987 : if (!per_ssa.needed_at_supernode_p (point.get_supernode ()))
1307 : {
1308 : /* Don't purge bindings of SSA names to svalues
1309 : that have unpurgable sm-state, so that leaks are
1310 : reported at the end of the function, rather than
1311 : at the last place that such an SSA name is referred to.
1312 :
1313 : But do purge them for temporaries (when SSA_NAME_VAR is
1314 : NULL), so that we report for cases where a leak happens when
1315 : a variable is overwritten with another value, so that the leak
1316 : is reported at the point of overwrite, rather than having
1317 : temporaries keep the value reachable until the frame is
1318 : popped. */
1319 232531 : const svalue *sval
1320 232531 : = new_state.m_region_model->get_store_value (reg, nullptr);
1321 232531 : if (!new_state.can_purge_p (eg.get_ext_state (), sval)
1322 257014 : && SSA_NAME_VAR (ssa_name))
1323 : {
1324 : /* (currently only state maps can keep things
1325 : alive). */
1326 18699 : if (logger)
1327 0 : logger->log ("not purging binding for %qE"
1328 : " (used by state map)", ssa_name);
1329 18699 : continue;
1330 : }
1331 :
1332 213832 : new_state.m_region_model->purge_region (reg);
1333 213832 : num_ssas_purged++;
1334 : }
1335 : }
1336 : else
1337 : {
1338 284408 : const tree decl = node;
1339 284408 : gcc_assert (TREE_CODE (node) == VAR_DECL
1340 : || TREE_CODE (node) == PARM_DECL
1341 : || TREE_CODE (node) == RESULT_DECL);
1342 568816 : if (const state_purge_per_decl *per_decl
1343 284408 : = pm->get_any_data_for_decl (decl))
1344 262901 : if (!per_decl->needed_at_supernode_p (point.get_supernode ()))
1345 : {
1346 : /* Don't purge bindings of decls if there are svalues
1347 : that have unpurgable sm-state within the decl's cluster,
1348 : so that leaks are reported at the end of the function,
1349 : rather than at the last place that such a decl is
1350 : referred to. */
1351 3530 : if (!new_state.can_purge_base_region_p (eg.get_ext_state (),
1352 : reg))
1353 : {
1354 : /* (currently only state maps can keep things
1355 : alive). */
1356 783 : if (logger)
1357 0 : logger->log ("not purging binding for %qE"
1358 : " (value in binding used by state map)",
1359 : decl);
1360 783 : continue;
1361 : }
1362 :
1363 2747 : new_state.m_region_model->purge_region (reg);
1364 2747 : num_decls_purged++;
1365 : }
1366 : }
1367 : }
1368 :
1369 393393 : if (num_ssas_purged > 0 || num_decls_purged > 0)
1370 : {
1371 164770 : if (logger)
1372 : {
1373 108 : logger->log ("num_ssas_purged: %i", num_ssas_purged);
1374 108 : logger->log ("num_decl_purged: %i", num_decls_purged);
1375 : }
1376 164770 : impl_region_model_context ctxt (eg, enode_for_diag,
1377 : this,
1378 : &new_state,
1379 : uncertainty,
1380 164770 : nullptr);
1381 164770 : detect_leaks (*this, new_state, nullptr, eg.get_ext_state (), &ctxt);
1382 164770 : }
1383 393393 : }
1384 :
1385 393771 : new_state.m_region_model->canonicalize ();
1386 :
1387 393771 : return new_state;
1388 397148 : }
1389 :
1390 : /* Return true if there are no unpurgeable bindings within BASE_REG. */
1391 :
1392 : bool
1393 3530 : program_state::can_purge_base_region_p (const extrinsic_state &ext_state,
1394 : const region *base_reg) const
1395 : {
1396 3530 : binding_cluster *cluster
1397 3530 : = m_region_model->get_store ()->get_cluster (base_reg);
1398 3530 : if (!cluster)
1399 : return true;
1400 :
1401 9115 : for (auto iter : *cluster)
1402 : {
1403 6368 : const svalue *sval = iter.m_sval;
1404 6368 : if (!can_purge_p (ext_state, sval))
1405 783 : return false;
1406 : }
1407 :
1408 2747 : return true;
1409 : }
1410 :
1411 : /* Get a representative tree to use for describing SVAL. */
1412 :
1413 : tree
1414 0 : program_state::get_representative_tree (const svalue *sval) const
1415 : {
1416 0 : gcc_assert (m_region_model);
1417 0 : return m_region_model->get_representative_tree (sval);
1418 : }
1419 :
1420 : /* Attempt to merge this state with OTHER, both at POINT.
1421 : Write the result to *OUT.
1422 : If the states were merged successfully, return true. */
1423 :
1424 : bool
1425 345838 : program_state::can_merge_with_p (const program_state &other,
1426 : const extrinsic_state &ext_state,
1427 : const program_point &point,
1428 : program_state *out) const
1429 : {
1430 345838 : gcc_assert (out);
1431 345838 : gcc_assert (m_region_model);
1432 :
1433 : /* Attempt to merge the sm-states. */
1434 : int i;
1435 : sm_state_map *smap;
1436 1765927 : FOR_EACH_VEC_ELT (out->m_checker_states, i, smap)
1437 3236334 : if (!m_checker_states[i]->can_merge_with_p (*other.m_checker_states[i],
1438 : ext_state.get_sm (i),
1439 : ext_state,
1440 1618167 : &out->m_checker_states[i]))
1441 : return false;
1442 :
1443 : /* Attempt to merge the region_models. */
1444 147760 : if (!m_region_model->can_merge_with_p (*other.m_region_model,
1445 : point,
1446 : out->m_region_model,
1447 : &ext_state,
1448 : this, &other))
1449 : return false;
1450 :
1451 39966 : out->m_region_model->canonicalize ();
1452 :
1453 39966 : return true;
1454 : }
1455 :
1456 : /* Assert that this object is valid. */
1457 :
1458 : void
1459 1718070 : program_state::validate (const extrinsic_state &ext_state) const
1460 : {
1461 : /* Skip this in a release build. */
1462 : #if !CHECKING_P
1463 : return;
1464 : #endif
1465 :
1466 3436140 : gcc_assert (m_checker_states.length () == ext_state.get_num_checkers ());
1467 1718070 : m_region_model->validate ();
1468 1718070 : }
1469 :
1470 : static void
1471 538 : log_set_of_svalues (logger *logger, const char *name,
1472 : const svalue_set &set)
1473 : {
1474 538 : logger->log ("%s", name);
1475 538 : logger->inc_indent ();
1476 538 : auto_vec<const svalue *> sval_vecs (set.elements ());
1477 538 : for (svalue_set::iterator iter = set.begin ();
1478 4772 : iter != set.end (); ++iter)
1479 2117 : sval_vecs.quick_push (*iter);
1480 538 : sval_vecs.qsort (svalue::cmp_ptr_ptr);
1481 : unsigned i;
1482 : const svalue *sval;
1483 2655 : FOR_EACH_VEC_ELT (sval_vecs, i, sval)
1484 : {
1485 2117 : logger->start_log_line ();
1486 2117 : pretty_printer *pp = logger->get_printer ();
1487 2117 : if (!flag_dump_noaddr)
1488 : {
1489 2117 : pp_pointer (pp, sval);
1490 2117 : pp_string (pp, ": ");
1491 : }
1492 2117 : sval->dump_to_pp (pp, false);
1493 2117 : logger->end_log_line ();
1494 : }
1495 538 : logger->dec_indent ();
1496 538 : }
1497 :
1498 : /* Compare the sets of svalues reachable from each of SRC_STATE and DEST_STATE.
1499 : For all svalues that are reachable in SRC_STATE and are not live in
1500 : DEST_STATE (whether explicitly reachable in DEST_STATE, or implicitly live
1501 : based on the former set), call CTXT->on_svalue_leak for them.
1502 :
1503 : Call on_liveness_change on both the CTXT and on the DEST_STATE's
1504 : constraint_manager, purging dead svalues from sm-state and from
1505 : constraints, respectively.
1506 :
1507 : This function should be called at each fine-grained state change, not
1508 : just at exploded edges. */
1509 :
1510 : void
1511 484105 : program_state::detect_leaks (const program_state &src_state,
1512 : const program_state &dest_state,
1513 : const svalue *extra_sval,
1514 : const extrinsic_state &ext_state,
1515 : region_model_context *ctxt)
1516 : {
1517 484105 : logger *logger = ext_state.get_logger ();
1518 484105 : LOG_SCOPE (logger);
1519 484105 : const uncertainty_t *uncertainty = ctxt->get_uncertainty ();
1520 484105 : if (logger)
1521 : {
1522 269 : pretty_printer *pp = logger->get_printer ();
1523 269 : logger->start_log_line ();
1524 269 : pp_string (pp, "src_state: ");
1525 269 : src_state.dump_to_pp (ext_state, true, false, pp);
1526 269 : logger->end_log_line ();
1527 269 : logger->start_log_line ();
1528 269 : pp_string (pp, "dest_state: ");
1529 269 : dest_state.dump_to_pp (ext_state, true, false, pp);
1530 269 : logger->end_log_line ();
1531 269 : if (extra_sval)
1532 : {
1533 1 : logger->start_log_line ();
1534 1 : pp_string (pp, "extra_sval: ");
1535 1 : extra_sval->dump_to_pp (pp, true);
1536 1 : logger->end_log_line ();
1537 : }
1538 269 : if (uncertainty)
1539 : {
1540 241 : logger->start_log_line ();
1541 241 : pp_string (pp, "uncertainty: ");
1542 241 : uncertainty->dump_to_pp (pp, true);
1543 241 : logger->end_log_line ();
1544 : }
1545 : }
1546 :
1547 : /* Get svalues reachable from each of src_state and dest_state.
1548 : Get svalues *known* to be reachable in src_state.
1549 : Pass in uncertainty for dest_state so that we additionally get svalues that
1550 : *might* still be reachable in dst_state. */
1551 484105 : svalue_set known_src_svalues;
1552 484105 : src_state.m_region_model->get_reachable_svalues (&known_src_svalues,
1553 : nullptr, nullptr);
1554 484105 : svalue_set maybe_dest_svalues;
1555 484105 : dest_state.m_region_model->get_reachable_svalues (&maybe_dest_svalues,
1556 : extra_sval, uncertainty);
1557 :
1558 484105 : if (logger)
1559 : {
1560 269 : log_set_of_svalues (logger, "src_state known reachable svalues:",
1561 : known_src_svalues);
1562 269 : log_set_of_svalues (logger, "dest_state maybe reachable svalues:",
1563 : maybe_dest_svalues);
1564 : }
1565 :
1566 484105 : auto_vec <const svalue *> dead_svals (known_src_svalues.elements ());
1567 4887252 : for (svalue_set::iterator iter = known_src_svalues.begin ();
1568 9290399 : iter != known_src_svalues.end (); ++iter)
1569 : {
1570 4403147 : const svalue *sval = (*iter);
1571 : /* For each sval reachable from SRC_STATE, determine if it is
1572 : live in DEST_STATE: either explicitly reachable, implicitly
1573 : live based on the set of explicitly reachable svalues,
1574 : or possibly reachable as recorded in uncertainty.
1575 : Record those that have ceased to be live i.e. were known
1576 : to be live, and are now not known to be even possibly-live. */
1577 4403147 : if (!sval->live_p (&maybe_dest_svalues, dest_state.m_region_model))
1578 86493 : dead_svals.quick_push (sval);
1579 : }
1580 :
1581 : /* Call CTXT->on_svalue_leak on all svals in SRC_STATE that have ceased
1582 : to be live, sorting them first to ensure deterministic behavior. */
1583 484105 : dead_svals.qsort (svalue::cmp_ptr_ptr);
1584 : unsigned i;
1585 : const svalue *sval;
1586 570598 : FOR_EACH_VEC_ELT (dead_svals, i, sval)
1587 86493 : ctxt->on_svalue_leak (sval);
1588 :
1589 : /* Purge dead svals from sm-state. */
1590 484105 : ctxt->on_liveness_change (maybe_dest_svalues,
1591 484105 : dest_state.m_region_model);
1592 :
1593 : /* Purge dead svals from constraints. */
1594 484105 : dest_state.m_region_model->get_constraints ()->on_liveness_change
1595 484105 : (maybe_dest_svalues, dest_state.m_region_model);
1596 :
1597 : /* Purge dead heap-allocated regions from dynamic extents. */
1598 1450598 : for (const svalue *sval : dead_svals)
1599 86493 : if (const region *reg = sval->maybe_get_region ())
1600 19286 : if (reg->get_kind () == RK_HEAP_ALLOCATED)
1601 6838 : dest_state.m_region_model->unset_dynamic_extents (reg);
1602 484105 : }
1603 :
1604 : /* Attempt to use R to replay SUMMARY into this object.
1605 : Return true if it is possible. */
1606 :
1607 : bool
1608 1541 : program_state::replay_call_summary (call_summary_replay &r,
1609 : const program_state &summary)
1610 : {
1611 1541 : if (!m_region_model->replay_call_summary (r, *summary.m_region_model))
1612 : return false;
1613 :
1614 11336 : for (unsigned sm_idx = 0; sm_idx < m_checker_states.length (); sm_idx++)
1615 : {
1616 9919 : const sm_state_map *summary_sm_map = summary.m_checker_states[sm_idx];
1617 9919 : m_checker_states[sm_idx]->replay_call_summary (r, *summary_sm_map);
1618 : }
1619 :
1620 1417 : if (!summary.m_valid)
1621 0 : m_valid = false;
1622 :
1623 : return true;
1624 : }
1625 :
1626 : /* Handle calls to "__analyzer_dump_state". */
1627 :
1628 : void
1629 357 : program_state::impl_call_analyzer_dump_state (const gcall &call,
1630 : const extrinsic_state &ext_state,
1631 : region_model_context *ctxt)
1632 : {
1633 357 : call_details cd (call, m_region_model, ctxt);
1634 357 : const char *sm_name = cd.get_arg_string_literal (0);
1635 357 : if (!sm_name)
1636 : {
1637 4 : error_at (call.location, "cannot determine state machine");
1638 12 : return;
1639 : }
1640 353 : unsigned sm_idx;
1641 353 : if (!ext_state.get_sm_idx_by_name (sm_name, &sm_idx))
1642 : {
1643 4 : error_at (call.location, "unrecognized state machine %qs", sm_name);
1644 4 : return;
1645 : }
1646 349 : const sm_state_map *smap = m_checker_states[sm_idx];
1647 :
1648 349 : const svalue *sval = cd.get_arg_svalue (1);
1649 :
1650 : /* Strip off cast to int (due to variadic args). */
1651 349 : if (const svalue *cast = sval->maybe_undo_cast ())
1652 5 : sval = cast;
1653 :
1654 349 : state_machine::state_t state = smap->get_state (sval, ext_state);
1655 349 : warning_at (call.location, 0, "state: %qs", state->get_name ());
1656 : }
1657 :
1658 : #if CHECKING_P
1659 :
1660 : namespace selftest {
1661 :
1662 : /* Tests for sm_state_map. */
1663 :
1664 : static void
1665 4 : test_sm_state_map ()
1666 : {
1667 4 : tree x = build_global_decl ("x", integer_type_node);
1668 4 : tree y = build_global_decl ("y", integer_type_node);
1669 4 : tree z = build_global_decl ("z", integer_type_node);
1670 :
1671 4 : std::unique_ptr<state_machine> sm = make_malloc_state_machine (nullptr);
1672 4 : state_machine::state_t start = sm->get_start_state ();
1673 4 : std::vector<std::unique_ptr<state_machine>> checkers;
1674 4 : const state_machine &borrowed_sm = *sm.get ();
1675 4 : checkers.push_back (std::move (sm));
1676 4 : region_model_manager mgr;
1677 4 : engine eng (mgr);
1678 4 : extrinsic_state ext_state (std::move (checkers), &eng);
1679 :
1680 : /* Test setting states on svalue_id instances directly. */
1681 4 : {
1682 4 : const state_machine::state test_state_42 ("test state 42", 42);
1683 4 : const state_machine::state_t TEST_STATE_42 = &test_state_42;
1684 4 : region_model model (&mgr);
1685 4 : const svalue *x_sval = model.get_rvalue (x, nullptr);
1686 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1687 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1688 :
1689 4 : sm_state_map map (borrowed_sm);
1690 4 : ASSERT_TRUE (map.is_empty_p ());
1691 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), start);
1692 :
1693 4 : map.impl_set_state (x_sval, TEST_STATE_42, z_sval, ext_state);
1694 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), TEST_STATE_42);
1695 4 : ASSERT_EQ (map.get_origin (x_sval, ext_state), z_sval);
1696 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), start);
1697 4 : ASSERT_FALSE (map.is_empty_p ());
1698 :
1699 4 : map.impl_set_state (y_sval, 0, z_sval, ext_state);
1700 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), start);
1701 :
1702 4 : map.impl_set_state (x_sval, 0, z_sval, ext_state);
1703 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), start);
1704 4 : ASSERT_TRUE (map.is_empty_p ());
1705 4 : }
1706 :
1707 4 : const state_machine::state test_state_5 ("test state 5", 5);
1708 4 : const state_machine::state_t TEST_STATE_5 = &test_state_5;
1709 :
1710 : /* Test setting states via equivalence classes. */
1711 4 : {
1712 4 : region_model model (&mgr);
1713 4 : const svalue *x_sval = model.get_rvalue (x, nullptr);
1714 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1715 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1716 :
1717 4 : sm_state_map map (borrowed_sm);
1718 4 : ASSERT_TRUE (map.is_empty_p ());
1719 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), start);
1720 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), start);
1721 :
1722 4 : model.add_constraint (x, EQ_EXPR, y, nullptr);
1723 :
1724 : /* Setting x to a state should also update y, as they
1725 : are in the same equivalence class. */
1726 4 : map.set_state (&model, x_sval, TEST_STATE_5, z_sval, ext_state);
1727 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), TEST_STATE_5);
1728 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), TEST_STATE_5);
1729 4 : ASSERT_EQ (map.get_origin (x_sval, ext_state), z_sval);
1730 4 : ASSERT_EQ (map.get_origin (y_sval, ext_state), z_sval);
1731 4 : }
1732 :
1733 : /* Test equality and hashing. */
1734 4 : {
1735 4 : region_model model (&mgr);
1736 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1737 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1738 :
1739 4 : sm_state_map map0 (borrowed_sm);
1740 4 : sm_state_map map1 (borrowed_sm);
1741 4 : sm_state_map map2 (borrowed_sm);
1742 :
1743 4 : ASSERT_EQ (map0.hash (), map1.hash ());
1744 4 : ASSERT_EQ (map0, map1);
1745 :
1746 4 : map1.impl_set_state (y_sval, TEST_STATE_5, z_sval, ext_state);
1747 4 : ASSERT_NE (map0.hash (), map1.hash ());
1748 4 : ASSERT_NE (map0, map1);
1749 :
1750 : /* Make the same change to map2. */
1751 4 : map2.impl_set_state (y_sval, TEST_STATE_5, z_sval, ext_state);
1752 4 : ASSERT_EQ (map1.hash (), map2.hash ());
1753 4 : ASSERT_EQ (map1, map2);
1754 4 : }
1755 :
1756 : /* Equality and hashing shouldn't depend on ordering. */
1757 4 : {
1758 4 : const state_machine::state test_state_2 ("test state 2", 2);
1759 4 : const state_machine::state_t TEST_STATE_2 = &test_state_2;
1760 4 : const state_machine::state test_state_3 ("test state 3", 3);
1761 4 : const state_machine::state_t TEST_STATE_3 = &test_state_3;
1762 4 : sm_state_map map0 (borrowed_sm);
1763 4 : sm_state_map map1 (borrowed_sm);
1764 4 : sm_state_map map2 (borrowed_sm);
1765 :
1766 4 : ASSERT_EQ (map0.hash (), map1.hash ());
1767 4 : ASSERT_EQ (map0, map1);
1768 :
1769 4 : region_model model (&mgr);
1770 4 : const svalue *x_sval = model.get_rvalue (x, nullptr);
1771 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1772 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1773 :
1774 4 : map1.impl_set_state (x_sval, TEST_STATE_2, nullptr, ext_state);
1775 4 : map1.impl_set_state (y_sval, TEST_STATE_3, nullptr, ext_state);
1776 4 : map1.impl_set_state (z_sval, TEST_STATE_2, nullptr, ext_state);
1777 :
1778 4 : map2.impl_set_state (z_sval, TEST_STATE_2, nullptr, ext_state);
1779 4 : map2.impl_set_state (y_sval, TEST_STATE_3, nullptr, ext_state);
1780 4 : map2.impl_set_state (x_sval, TEST_STATE_2, nullptr, ext_state);
1781 :
1782 4 : ASSERT_EQ (map1.hash (), map2.hash ());
1783 4 : ASSERT_EQ (map1, map2);
1784 4 : }
1785 :
1786 : // TODO: coverage for purging
1787 4 : }
1788 :
1789 : /* Check program_state works as expected. */
1790 :
1791 : static void
1792 4 : test_program_state_1 ()
1793 : {
1794 : /* Create a program_state for a global ptr "p" that has
1795 : malloc sm-state, pointing to a region on the heap. */
1796 4 : tree p = build_global_decl ("p", ptr_type_node);
1797 :
1798 4 : std::unique_ptr<state_machine> sm = make_malloc_state_machine (nullptr);
1799 4 : const state_machine::state_t UNCHECKED_STATE
1800 4 : = sm->get_state_by_name ("unchecked");
1801 :
1802 4 : region_model_manager mgr;
1803 4 : engine eng (mgr);
1804 4 : extrinsic_state ext_state (std::move (sm), &eng);
1805 4 : program_state s (ext_state);
1806 4 : region_model *model = s.m_region_model;
1807 4 : const svalue *size_in_bytes
1808 4 : = mgr.get_or_create_unknown_svalue (size_type_node);
1809 4 : const region *new_reg
1810 4 : = model->get_or_create_region_for_heap_alloc (size_in_bytes, nullptr);
1811 4 : const svalue *ptr_sval = mgr.get_ptr_svalue (ptr_type_node, new_reg);
1812 4 : model->set_value (model->get_lvalue (p, nullptr),
1813 : ptr_sval, nullptr);
1814 4 : sm_state_map *smap = s.m_checker_states[0];
1815 :
1816 4 : smap->impl_set_state (ptr_sval, UNCHECKED_STATE, nullptr, ext_state);
1817 4 : ASSERT_EQ (smap->get_state (ptr_sval, ext_state), UNCHECKED_STATE);
1818 4 : }
1819 :
1820 : /* Check that program_state works for string literals. */
1821 :
1822 : static void
1823 4 : test_program_state_2 ()
1824 : {
1825 : /* Create a program_state for a global ptr "p" that points to
1826 : a string constant. */
1827 4 : tree p = build_global_decl ("p", ptr_type_node);
1828 :
1829 4 : tree string_cst_ptr = build_string_literal (4, "foo");
1830 :
1831 4 : std::vector<std::unique_ptr<state_machine>> checkers;
1832 4 : region_model_manager mgr;
1833 4 : engine eng (mgr);
1834 4 : extrinsic_state ext_state (std::move (checkers), &eng);
1835 :
1836 4 : program_state s (ext_state);
1837 4 : region_model *model = s.m_region_model;
1838 4 : const region *p_reg = model->get_lvalue (p, nullptr);
1839 4 : const svalue *str_sval = model->get_rvalue (string_cst_ptr, nullptr);
1840 4 : model->set_value (p_reg, str_sval, nullptr);
1841 4 : }
1842 :
1843 : /* Verify that program_states with identical sm-state can be merged,
1844 : and that the merged program_state preserves the sm-state. */
1845 :
1846 : static void
1847 4 : test_program_state_merging ()
1848 : {
1849 : /* Create a program_state for a global ptr "p" that has
1850 : malloc sm-state, pointing to a region on the heap. */
1851 4 : tree p = build_global_decl ("p", ptr_type_node);
1852 :
1853 4 : region_model_manager mgr;
1854 4 : engine eng (mgr);
1855 4 : program_point point (program_point::origin (mgr));
1856 4 : extrinsic_state ext_state (make_malloc_state_machine (nullptr),
1857 4 : &eng);
1858 :
1859 4 : program_state s0 (ext_state);
1860 4 : uncertainty_t uncertainty;
1861 4 : impl_region_model_context ctxt (&s0, ext_state, &uncertainty);
1862 :
1863 4 : region_model *model0 = s0.m_region_model;
1864 4 : const svalue *size_in_bytes
1865 4 : = mgr.get_or_create_unknown_svalue (size_type_node);
1866 4 : const region *new_reg
1867 4 : = model0->get_or_create_region_for_heap_alloc (size_in_bytes, nullptr);
1868 4 : const svalue *ptr_sval = mgr.get_ptr_svalue (ptr_type_node, new_reg);
1869 4 : model0->set_value (model0->get_lvalue (p, &ctxt),
1870 : ptr_sval, &ctxt);
1871 4 : sm_state_map *smap = s0.m_checker_states[0];
1872 4 : const state_machine::state test_state ("test state", 0);
1873 4 : const state_machine::state_t TEST_STATE = &test_state;
1874 4 : smap->impl_set_state (ptr_sval, TEST_STATE, nullptr, ext_state);
1875 4 : ASSERT_EQ (smap->get_state (ptr_sval, ext_state), TEST_STATE);
1876 :
1877 4 : model0->canonicalize ();
1878 :
1879 : /* Verify that canonicalization preserves sm-state. */
1880 4 : ASSERT_EQ (smap->get_state (model0->get_rvalue (p, nullptr), ext_state),
1881 : TEST_STATE);
1882 :
1883 : /* Make a copy of the program_state. */
1884 4 : program_state s1 (s0);
1885 4 : ASSERT_EQ (s0, s1);
1886 :
1887 : /* We have two identical states with "p" pointing to a heap region
1888 : with the given sm-state.
1889 : They ought to be mergeable, preserving the sm-state. */
1890 4 : program_state merged (ext_state);
1891 4 : ASSERT_TRUE (s0.can_merge_with_p (s1, ext_state, point, &merged));
1892 4 : merged.validate (ext_state);
1893 :
1894 : /* Verify that the merged state has the sm-state for "p". */
1895 4 : region_model *merged_model = merged.m_region_model;
1896 4 : sm_state_map *merged_smap = merged.m_checker_states[0];
1897 4 : ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, nullptr),
1898 : ext_state),
1899 : TEST_STATE);
1900 :
1901 : /* Try canonicalizing. */
1902 4 : merged.m_region_model->canonicalize ();
1903 4 : merged.validate (ext_state);
1904 :
1905 : /* Verify that the merged state still has the sm-state for "p". */
1906 4 : ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, nullptr),
1907 : ext_state),
1908 : TEST_STATE);
1909 :
1910 : /* After canonicalization, we ought to have equality with the inputs. */
1911 4 : ASSERT_EQ (s0, merged);
1912 8 : }
1913 :
1914 : /* Verify that program_states with different global-state in an sm-state
1915 : can't be merged. */
1916 :
1917 : static void
1918 4 : test_program_state_merging_2 ()
1919 : {
1920 4 : region_model_manager mgr;
1921 4 : engine eng (mgr);
1922 4 : program_point point (program_point::origin (mgr));
1923 4 : extrinsic_state ext_state (make_signal_state_machine (nullptr), &eng);
1924 :
1925 4 : const state_machine::state test_state_0 ("test state 0", 0);
1926 4 : const state_machine::state test_state_1 ("test state 1", 1);
1927 4 : const state_machine::state_t TEST_STATE_0 = &test_state_0;
1928 4 : const state_machine::state_t TEST_STATE_1 = &test_state_1;
1929 :
1930 4 : program_state s0 (ext_state);
1931 4 : {
1932 4 : sm_state_map *smap0 = s0.m_checker_states[0];
1933 4 : smap0->set_global_state (TEST_STATE_0);
1934 4 : ASSERT_EQ (smap0->get_global_state (), TEST_STATE_0);
1935 : }
1936 :
1937 4 : program_state s1 (ext_state);
1938 4 : {
1939 4 : sm_state_map *smap1 = s1.m_checker_states[0];
1940 4 : smap1->set_global_state (TEST_STATE_1);
1941 4 : ASSERT_EQ (smap1->get_global_state (), TEST_STATE_1);
1942 : }
1943 :
1944 4 : ASSERT_NE (s0, s1);
1945 :
1946 : /* They ought to not be mergeable. */
1947 4 : program_state merged (ext_state);
1948 4 : ASSERT_FALSE (s0.can_merge_with_p (s1, ext_state, point, &merged));
1949 4 : }
1950 :
1951 : /* Run all of the selftests within this file. */
1952 :
1953 : void
1954 4 : analyzer_program_state_cc_tests ()
1955 : {
1956 4 : test_sm_state_map ();
1957 4 : test_program_state_1 ();
1958 4 : test_program_state_2 ();
1959 4 : test_program_state_merging ();
1960 4 : test_program_state_merging_2 ();
1961 4 : }
1962 :
1963 : } // namespace selftest
1964 :
1965 : #endif /* CHECKING_P */
1966 :
1967 : } // namespace ana
1968 :
1969 : #endif /* #if ENABLE_ANALYZER */
|
