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