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 : : #include "diagnostic-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 : 11421720 : extrinsic_state::get_model_manager () const
114 : : {
115 : 11421720 : if (m_engine)
116 : 11421720 : 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 : 678394 : extrinsic_state::get_sm_idx_by_name (const char *name, unsigned *out) const
127 : : {
128 : 2710724 : for (size_t i = 0; i < m_checkers.size (); ++i)
129 : 2710212 : if (0 == strcmp (name, m_checkers[i]->get_name ()))
130 : : {
131 : : /* Found NAME. */
132 : 677882 : *out = i;
133 : 677882 : return true;
134 : : }
135 : :
136 : : /* NAME not found. */
137 : : return false;
138 : : }
139 : :
140 : : /* struct sm_state_map::entry_t. */
141 : :
142 : : int
143 : 96643 : sm_state_map::entry_t::cmp (const entry_t &entry_a, const entry_t &entry_b)
144 : : {
145 : 96643 : gcc_assert (entry_a.m_state);
146 : 96643 : gcc_assert (entry_b.m_state);
147 : 96643 : if (int cmp_state = ((int)entry_a.m_state->get_id ()
148 : 96643 : - (int)entry_b.m_state->get_id ()))
149 : : return cmp_state;
150 : 91012 : if (entry_a.m_origin && entry_b.m_origin)
151 : 0 : return svalue::cmp_ptr (entry_a.m_origin, entry_b.m_origin);
152 : 91012 : if (entry_a.m_origin)
153 : : return 1;
154 : 91012 : 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 : 2557011 : sm_state_map::sm_state_map (const state_machine &sm)
164 : 2557011 : : m_sm (sm), m_map (), m_global_state (sm.get_start_state ())
165 : : {
166 : 2557011 : }
167 : :
168 : : /* Clone the sm_state_map. */
169 : :
170 : : sm_state_map *
171 : 20234730 : sm_state_map::clone () const
172 : : {
173 : 20234730 : 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 : 498 : sm_state_map::print (const region_model *model,
182 : : bool simple, bool multiline,
183 : : pretty_printer *pp) const
184 : : {
185 : 498 : bool first = true;
186 : 498 : if (!multiline)
187 : 98 : pp_string (pp, "{");
188 : 996 : 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 : 498 : auto_vec <const svalue *> keys (m_map.elements ());
199 : 498 : for (map_t::iterator iter = m_map.begin ();
200 : 1275 : iter != m_map.end ();
201 : 777 : ++iter)
202 : 777 : keys.quick_push ((*iter).first);
203 : 498 : keys.qsort (svalue::cmp_ptr_ptr);
204 : : unsigned i;
205 : : const svalue *sval;
206 : 1275 : FOR_EACH_VEC_ELT (keys, i, sval)
207 : : {
208 : 777 : if (multiline)
209 : 676 : pp_string (pp, " ");
210 : 101 : else if (!first)
211 : 3 : pp_string (pp, ", ");
212 : 777 : first = false;
213 : 777 : if (!flag_dump_noaddr)
214 : : {
215 : 777 : pp_pointer (pp, sval);
216 : 777 : pp_string (pp, ": ");
217 : : }
218 : 777 : sval->dump_to_pp (pp, simple);
219 : :
220 : 777 : entry_t e = *const_cast <map_t &> (m_map).get (sval);
221 : 777 : pp_string (pp, ": ");
222 : 777 : e.m_state->dump_to_pp (pp);
223 : 777 : if (model)
224 : 777 : if (tree rep = model->get_representative_tree (sval))
225 : : {
226 : 735 : pp_string (pp, " (");
227 : 735 : dump_quoted_tree (pp, rep);
228 : 735 : pp_character (pp, ')');
229 : : }
230 : 777 : 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 : 777 : if (multiline)
249 : 676 : pp_newline (pp);
250 : : }
251 : 498 : if (!multiline)
252 : 98 : pp_string (pp, "}");
253 : 498 : }
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 : 11083 : sm_state_map::is_empty_p () const
375 : : {
376 : 11083 : 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 : 8565834 : sm_state_map::hash () const
383 : : {
384 : 8565834 : 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 : 8565834 : for (map_t::iterator iter = m_map.begin ();
390 : 9715621 : iter != m_map.end ();
391 : 1149787 : ++iter)
392 : : {
393 : 1149787 : inchash::hash hstate;
394 : 1149787 : hstate.add_ptr ((*iter).first);
395 : 1149787 : entry_t e = (*iter).second;
396 : 1149787 : hstate.add_int (e.m_state->get_id ());
397 : 1149787 : hstate.add_ptr (e.m_origin);
398 : 1149787 : result ^= hstate.end ();
399 : : }
400 : 8565834 : result ^= m_global_state->get_id ();
401 : :
402 : 8565834 : return result;
403 : : }
404 : :
405 : : /* Equality operator for sm_state_map. */
406 : :
407 : : bool
408 : 2915124 : sm_state_map::operator== (const sm_state_map &other) const
409 : : {
410 : 2915124 : if (m_global_state != other.m_global_state)
411 : : return false;
412 : :
413 : 2912970 : if (m_map.elements () != other.m_map.elements ())
414 : : return false;
415 : :
416 : 2744097 : for (map_t::iterator iter = m_map.begin ();
417 : 3153678 : iter != m_map.end ();
418 : 409581 : ++iter)
419 : : {
420 : 440618 : const svalue *sval = (*iter).first;
421 : 440618 : entry_t e = (*iter).second;
422 : 440618 : entry_t *other_slot = const_cast <map_t &> (other.m_map).get (sval);
423 : 440618 : if (other_slot == nullptr)
424 : 31037 : return false;
425 : 850199 : if (e != *other_slot)
426 : : return false;
427 : : }
428 : :
429 : 2713060 : 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 : 8718582 : sm_state_map::get_state (const svalue *sval,
439 : : const extrinsic_state &ext_state) const
440 : : {
441 : 8718582 : gcc_assert (sval);
442 : :
443 : 8718582 : sval = canonicalize_svalue (sval, ext_state);
444 : :
445 : 17437164 : if (entry_t *slot
446 : 8718582 : = const_cast <map_t &> (m_map).get (sval))
447 : 659087 : 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 : 8059495 : if (m_sm.inherited_state_p ())
455 : 2495509 : if (region_model_manager *mgr = ext_state.get_model_manager ())
456 : : {
457 : 2495509 : if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
458 : : {
459 : 274052 : const region *reg = init_sval->get_region ();
460 : : /* Try recursing upwards (up to the base region for the
461 : : cluster). */
462 : 274052 : if (!reg->base_region_p ())
463 : 63651 : if (const region *parent_reg = reg->get_parent_region ())
464 : : {
465 : 63651 : const svalue *parent_init_sval
466 : 63651 : = mgr->get_or_create_initial_value (parent_reg);
467 : 63651 : state_machine::state_t parent_state
468 : 63651 : = get_state (parent_init_sval, ext_state);
469 : 63651 : if (parent_state)
470 : : return parent_state;
471 : : }
472 : : }
473 : 2221457 : else if (const sub_svalue *sub_sval = sval->dyn_cast_sub_svalue ())
474 : : {
475 : 10789 : const svalue *parent_sval = sub_sval->get_parent ();
476 : 21578 : if (state_machine::state_t parent_state
477 : 10789 : = get_state (parent_sval, ext_state))
478 : : return parent_state;
479 : : }
480 : : }
481 : :
482 : 15970110 : if (state_machine::state_t state
483 : 7985055 : = m_sm.alt_get_inherited_state (*this, sval, ext_state))
484 : : return state;
485 : :
486 : 7858111 : 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 : 42416 : 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 : 42416 : if (model == nullptr)
518 : : return;
519 : :
520 : : /* Reject attempts to set state on UNKNOWN/POISONED. */
521 : 42416 : if (!sval->can_have_associated_state_p ())
522 : : return;
523 : :
524 : 36961 : equiv_class &ec = model->get_constraints ()->get_equiv_class (sval);
525 : 36961 : 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 : 36961 : 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 : 36961 : bool any_changed = false;
540 : 149545 : for (const svalue *sval : ec.m_vars)
541 : 38662 : any_changed |= impl_set_state (sval, state, origin, ext_state);
542 : 36961 : 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 : 194146 : 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 : 194146 : sval = canonicalize_svalue (sval, ext_state);
555 : :
556 : 194146 : if (get_state (sval, ext_state) == state)
557 : : return false;
558 : :
559 : 150603 : gcc_assert (sval->can_have_associated_state_p ());
560 : :
561 : 150603 : if (m_sm.inherited_state_p ())
562 : : {
563 : 30272 : if (const compound_svalue *compound_sval
564 : 15136 : = sval->dyn_cast_compound_svalue ())
565 : 0 : for (auto iter : *compound_sval)
566 : : {
567 : 0 : const svalue *inner_sval = iter.second;
568 : 0 : if (inner_sval->can_have_associated_state_p ())
569 : 0 : impl_set_state (inner_sval, state, origin, ext_state);
570 : : }
571 : : }
572 : :
573 : : /* Special-case state 0 as the default value. */
574 : 150603 : if (state == 0)
575 : : {
576 : 1377 : if (m_map.get (sval))
577 : 1373 : m_map.remove (sval);
578 : 1377 : return true;
579 : : }
580 : 149226 : gcc_assert (sval);
581 : 149226 : m_map.put (sval, entry_t (state, origin));
582 : 149226 : return true;
583 : : }
584 : :
585 : : /* Clear any state for SVAL from this state map. */
586 : :
587 : : void
588 : 2715 : sm_state_map::clear_any_state (const svalue *sval)
589 : : {
590 : 2715 : m_map.remove (sval);
591 : 2715 : }
592 : :
593 : : /* Clear all per-svalue state within this state map. */
594 : :
595 : : void
596 : 8968 : sm_state_map::clear_all_per_svalue_state ()
597 : : {
598 : 8968 : m_map.empty ();
599 : 8968 : }
600 : :
601 : : /* Set the "global" state within this state map to STATE. */
602 : :
603 : : void
604 : 202486 : sm_state_map::set_global_state (state_machine::state_t state)
605 : : {
606 : 202486 : m_global_state = state;
607 : 202486 : }
608 : :
609 : : /* Get the "global" state within this state map. */
610 : :
611 : : state_machine::state_t
612 : 1344312 : sm_state_map::get_global_state () const
613 : : {
614 : 1344312 : return m_global_state;
615 : : }
616 : :
617 : : /* Purge any state for SVAL.
618 : : If !SM::can_purge_p, then report the state as leaking,
619 : : using CTXT. */
620 : :
621 : : void
622 : 526731 : sm_state_map::on_svalue_leak (const svalue *sval,
623 : : impl_region_model_context *ctxt)
624 : : {
625 : 526731 : if (state_machine::state_t state = get_state (sval, ctxt->m_ext_state))
626 : : {
627 : 526731 : if (m_sm.can_purge_p (state))
628 : 526039 : m_map.remove (sval);
629 : : else
630 : 692 : ctxt->on_state_leak (m_sm, sval, state);
631 : : }
632 : 526731 : }
633 : :
634 : : /* Purge any state for svalues that aren't live with respect to LIVE_SVALUES
635 : : and MODEL. */
636 : :
637 : : void
638 : 4118543 : sm_state_map::on_liveness_change (const svalue_set &live_svalues,
639 : : const region_model *model,
640 : : const extrinsic_state &ext_state,
641 : : impl_region_model_context *ctxt)
642 : : {
643 : 4118543 : svalue_set svals_to_unset;
644 : 4118543 : uncertainty_t *uncertainty = ctxt->get_uncertainty ();
645 : :
646 : 4118543 : auto_vec<const svalue *> leaked_svals (m_map.elements ());
647 : 4701374 : for (map_t::iterator iter = m_map.begin ();
648 : 4701374 : iter != m_map.end ();
649 : 582831 : ++iter)
650 : : {
651 : 582831 : const svalue *iter_sval = (*iter).first;
652 : 582831 : if (!iter_sval->live_p (&live_svalues, model))
653 : : {
654 : 12530 : svals_to_unset.add (iter_sval);
655 : 12530 : entry_t e = (*iter).second;
656 : 12530 : if (!m_sm.can_purge_p (e.m_state))
657 : 1192 : leaked_svals.quick_push (iter_sval);
658 : : }
659 : 582831 : if (uncertainty)
660 : 582831 : if (uncertainty->unknown_sm_state_p (iter_sval))
661 : 602 : svals_to_unset.add (iter_sval);
662 : : }
663 : :
664 : 4118543 : leaked_svals.qsort (svalue::cmp_ptr_ptr);
665 : :
666 : : unsigned i;
667 : : const svalue *sval;
668 : 4119735 : FOR_EACH_VEC_ELT (leaked_svals, i, sval)
669 : : {
670 : 1192 : entry_t e = *m_map.get (sval);
671 : 1192 : ctxt->on_state_leak (m_sm, sval, e.m_state);
672 : : }
673 : :
674 : 4118543 : sm_state_map old_sm_map = *this;
675 : :
676 : 4118543 : for (svalue_set::iterator iter = svals_to_unset.begin ();
677 : 4144807 : iter != svals_to_unset.end (); ++iter)
678 : 13132 : m_map.remove (*iter);
679 : :
680 : : /* For state machines like "taint" where states can be
681 : : alt-inherited from other svalues, ensure that state purging doesn't
682 : : make us lose sm-state.
683 : :
684 : : Consider e.g.:
685 : :
686 : : make_tainted(foo);
687 : : if (foo.field > 128)
688 : : return;
689 : : arr[foo.field].f1 = v1;
690 : :
691 : : where the last line is:
692 : :
693 : : (A): _t1 = foo.field;
694 : : (B): _t2 = _t1 * sizeof(arr[0]);
695 : : (C): [arr + _t2].f1 = val;
696 : :
697 : : At (A), foo is 'tainted' and foo.field is 'has_ub'.
698 : : After (B), foo.field's value (in _t1) is no longer directly
699 : : within LIVE_SVALUES, so with state purging enabled, we would
700 : : erroneously purge the "has_ub" state from the svalue.
701 : :
702 : : Given that _t2's value's state comes from _t1's value's state,
703 : : we need to preserve that information.
704 : :
705 : : Hence for all svalues that have had their explicit sm-state unset,
706 : : having their sm-state being unset, determine if doing so has changed
707 : : their effective state, and if so, explicitly set their state.
708 : :
709 : : For example, in the above, unsetting the "has_ub" for _t1's value means
710 : : that _t2's effective value changes from "has_ub" (from alt-inherited
711 : : from _t1's value) to "tainted" (inherited from "foo"'s value).
712 : :
713 : : For such cases, preserve the effective state by explicitly setting the
714 : : new state. In the above example, this means explicitly setting _t2's
715 : : value to the value ("has_ub") it was previously alt-inheriting from _t1's
716 : : value. */
717 : 4118543 : if (m_sm.has_alt_get_inherited_state_p ())
718 : : {
719 : 588233 : auto_vec<const svalue *> svalues_needing_state;
720 : 608723 : for (auto unset_sval : svals_to_unset)
721 : : {
722 : 10245 : const state_machine::state_t old_state
723 : 10245 : = old_sm_map.get_state (unset_sval, ext_state);
724 : 10245 : const state_machine::state_t new_state
725 : 10245 : = get_state (unset_sval, ext_state);
726 : 10245 : if (new_state != old_state)
727 : 10245 : svalues_needing_state.safe_push (unset_sval);
728 : : }
729 : 613578 : for (auto sval : svalues_needing_state)
730 : : {
731 : 10245 : const state_machine::state_t old_state
732 : 10245 : = old_sm_map.get_state (sval, ext_state);
733 : 10245 : impl_set_state (sval, old_state, nullptr, ext_state);
734 : : }
735 : 588233 : }
736 : 4118543 : }
737 : :
738 : : /* Purge state from SVAL (in response to a call to an unknown function). */
739 : :
740 : : void
741 : 347850 : sm_state_map::on_unknown_change (const svalue *sval,
742 : : bool is_mutable,
743 : : const extrinsic_state &ext_state)
744 : : {
745 : 347850 : svalue_set svals_to_unset;
746 : :
747 : 382146 : for (map_t::iterator iter = m_map.begin ();
748 : 382146 : iter != m_map.end ();
749 : 34296 : ++iter)
750 : : {
751 : 34296 : const svalue *key = (*iter).first;
752 : 34296 : entry_t e = (*iter).second;
753 : : /* We only want to purge state for some states when things
754 : : are mutable. For example, in sm-malloc.cc, an on-stack ptr
755 : : doesn't stop being stack-allocated when passed to an unknown fn. */
756 : 34296 : if (!m_sm.reset_when_passed_to_unknown_fn_p (e.m_state, is_mutable))
757 : 15881 : continue;
758 : 18415 : if (key == sval)
759 : 1231 : svals_to_unset.add (key);
760 : : /* If we have INIT_VAL(BASE_REG), then unset any INIT_VAL(REG)
761 : : for REG within BASE_REG. */
762 : 18415 : if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
763 : 3387 : if (const initial_svalue *init_key = key->dyn_cast_initial_svalue ())
764 : : {
765 : 1591 : const region *changed_reg = init_sval->get_region ();
766 : 1591 : const region *changed_key = init_key->get_region ();
767 : 1591 : if (changed_key->get_base_region () == changed_reg)
768 : 245 : svals_to_unset.add (key);
769 : : }
770 : : }
771 : :
772 : 349082 : for (svalue_set::iterator iter = svals_to_unset.begin ();
773 : 698164 : iter != svals_to_unset.end (); ++iter)
774 : 1232 : impl_set_state (*iter, (state_machine::state_t)0, nullptr, ext_state);
775 : 347850 : }
776 : :
777 : : /* Purge state for things involving SVAL.
778 : : For use when SVAL changes meaning, at the def_stmt on an SSA_NAME. */
779 : :
780 : : void
781 : 155435 : sm_state_map::purge_state_involving (const svalue *sval,
782 : : const extrinsic_state &ext_state)
783 : : {
784 : : /* Currently svalue::involves_p requires this. */
785 : 310870 : if (!(sval->get_kind () == SK_INITIAL
786 : 155435 : || sval->get_kind () == SK_CONJURED))
787 : 0 : return;
788 : :
789 : 155435 : svalue_set svals_to_unset;
790 : :
791 : 181157 : for (map_t::iterator iter = m_map.begin ();
792 : 181157 : iter != m_map.end ();
793 : 25722 : ++iter)
794 : : {
795 : 25722 : const svalue *key = (*iter).first;
796 : 25722 : entry_t e = (*iter).second;
797 : 25722 : if (!m_sm.can_purge_p (e.m_state))
798 : 9714 : continue;
799 : 16008 : if (key->involves_p (sval))
800 : 137 : svals_to_unset.add (key);
801 : : }
802 : :
803 : 155572 : for (svalue_set::iterator iter = svals_to_unset.begin ();
804 : 311144 : iter != svals_to_unset.end (); ++iter)
805 : 137 : impl_set_state (*iter, (state_machine::state_t)0, nullptr, ext_state);
806 : 155435 : }
807 : :
808 : : /* Comparator for imposing an order on sm_state_map instances. */
809 : :
810 : : int
811 : 526649 : sm_state_map::cmp (const sm_state_map &smap_a, const sm_state_map &smap_b)
812 : : {
813 : 526649 : if (int cmp_count = smap_a.elements () - smap_b.elements ())
814 : : return cmp_count;
815 : :
816 : 460447 : auto_vec <const svalue *> keys_a (smap_a.elements ());
817 : 460447 : for (map_t::iterator iter = smap_a.begin ();
818 : 585797 : iter != smap_a.end ();
819 : 125350 : ++iter)
820 : 125350 : keys_a.quick_push ((*iter).first);
821 : 460447 : keys_a.qsort (svalue::cmp_ptr_ptr);
822 : :
823 : 460447 : auto_vec <const svalue *> keys_b (smap_b.elements ());
824 : 460447 : for (map_t::iterator iter = smap_b.begin ();
825 : 585797 : iter != smap_b.end ();
826 : 125350 : ++iter)
827 : 125350 : keys_b.quick_push ((*iter).first);
828 : 460447 : keys_b.qsort (svalue::cmp_ptr_ptr);
829 : :
830 : : unsigned i;
831 : : const svalue *sval_a;
832 : 615899 : FOR_EACH_VEC_ELT (keys_a, i, sval_a)
833 : : {
834 : 107917 : const svalue *sval_b = keys_b[i];
835 : 107917 : if (int cmp_sval = svalue::cmp_ptr (sval_a, sval_b))
836 : 16905 : return cmp_sval;
837 : 96643 : const entry_t *e_a = const_cast <map_t &> (smap_a.m_map).get (sval_a);
838 : 96643 : const entry_t *e_b = const_cast <map_t &> (smap_b.m_map).get (sval_b);
839 : 96643 : if (int cmp_entry = entry_t::cmp (*e_a, *e_b))
840 : : return cmp_entry;
841 : : }
842 : :
843 : : return 0;
844 : 460447 : }
845 : :
846 : : /* Canonicalize SVAL before getting/setting it within the map.
847 : : Convert all NULL pointers to (void *) to avoid state explosions
848 : : involving all of the various (foo *)NULL vs (bar *)NULL. */
849 : :
850 : : const svalue *
851 : 8912740 : sm_state_map::canonicalize_svalue (const svalue *sval,
852 : : const extrinsic_state &ext_state)
853 : : {
854 : 8912740 : region_model_manager *mgr = ext_state.get_model_manager ();
855 : 8912740 : if (mgr && sval->get_type () && POINTER_TYPE_P (sval->get_type ()))
856 : 3107809 : if (tree cst = sval->maybe_get_constant ())
857 : 56334 : if (zerop (cst))
858 : 52417 : return mgr->get_or_create_constant_svalue (null_pointer_node);
859 : :
860 : : return sval;
861 : : }
862 : :
863 : : /* Attempt to merge this state map with OTHER, writing the result
864 : : into *OUT.
865 : : Return true if the merger was possible, false otherwise.
866 : :
867 : : Normally, only identical state maps can be merged, so that
868 : : differences between state maps lead to different enodes
869 : :
870 : : However some state machines may support merging states to
871 : : allow for discarding of less important states, and thus avoid
872 : : blow-up of the exploded graph. */
873 : :
874 : : bool
875 : 1365127 : sm_state_map::can_merge_with_p (const sm_state_map &other,
876 : : const state_machine &sm,
877 : : const extrinsic_state &ext_state,
878 : : sm_state_map **out) const
879 : : {
880 : : /* If identical, then they merge trivially, with a copy. */
881 : 1365127 : if (*this == other)
882 : : {
883 : 2364590 : delete *out;
884 : 1182295 : *out = clone ();
885 : 1182295 : return true;
886 : : }
887 : :
888 : 365664 : delete *out;
889 : 182832 : *out = new sm_state_map (sm);
890 : :
891 : : /* Otherwise, attempt to merge element by element. */
892 : :
893 : : /* Try to merge global state. */
894 : 365664 : if (state_machine::state_t merged_global_state
895 : 184488 : = sm.maybe_get_merged_state (get_global_state (),
896 : : other.get_global_state ()))
897 : 181176 : (*out)->set_global_state (merged_global_state);
898 : : else
899 : : return false;
900 : :
901 : : /* Try to merge state each svalue's state (for the union
902 : : of svalues represented by each smap).
903 : : Ignore the origin information. */
904 : 181176 : hash_set<const svalue *> svals;
905 : 626520 : for (auto kv : *this)
906 : 445344 : svals.add (kv.first);
907 : 492126 : for (auto kv : other)
908 : 310950 : svals.add (kv.first);
909 : 468812 : for (auto sval : svals)
910 : : {
911 : 301724 : state_machine::state_t this_state = get_state (sval, ext_state);
912 : 301724 : state_machine::state_t other_state = other.get_state (sval, ext_state);
913 : 301724 : if (state_machine::state_t merged_state
914 : 301724 : = sm.maybe_get_merged_state (this_state, other_state))
915 : 143818 : (*out)->impl_set_state (sval, merged_state, nullptr, ext_state);
916 : : else
917 : 157906 : return false;
918 : : }
919 : :
920 : : /* Successfully merged all elements. */
921 : 23270 : return true;
922 : 181176 : }
923 : :
924 : : /* class program_state. */
925 : :
926 : : /* program_state's ctor. */
927 : :
928 : 339239 : program_state::program_state (const extrinsic_state &ext_state)
929 : 339239 : : m_region_model (nullptr),
930 : 339239 : m_checker_states (ext_state.get_num_checkers ()),
931 : 339239 : m_valid (true)
932 : : {
933 : 339239 : engine *eng = ext_state.get_engine ();
934 : 339239 : region_model_manager *mgr = eng->get_model_manager ();
935 : 339239 : m_region_model = new region_model (mgr);
936 : 339239 : const int num_states = ext_state.get_num_checkers ();
937 : 2713386 : for (int i = 0; i < num_states; i++)
938 : : {
939 : 2374147 : sm_state_map *sm = new sm_state_map (ext_state.get_sm (i));
940 : 2374147 : m_checker_states.quick_push (sm);
941 : : }
942 : 339239 : }
943 : :
944 : : /* Attempt to use R to replay SUMMARY into this object.
945 : : Return true if it is possible. */
946 : :
947 : : bool
948 : 9107 : sm_state_map::replay_call_summary (call_summary_replay &r,
949 : : const sm_state_map &summary)
950 : : {
951 : 12937 : for (auto kv : summary.m_map)
952 : : {
953 : 1915 : const svalue *summary_sval = kv.first;
954 : 1915 : const svalue *caller_sval = r.convert_svalue_from_summary (summary_sval);
955 : 1915 : if (!caller_sval)
956 : 495 : continue;
957 : 1915 : if (!caller_sval->can_have_associated_state_p ())
958 : 495 : continue;
959 : 1420 : const svalue *summary_origin = kv.second.m_origin;
960 : 1420 : const svalue *caller_origin
961 : : = (summary_origin
962 : 1420 : ? r.convert_svalue_from_summary (summary_origin)
963 : : : nullptr);
964 : : // caller_origin can be nullptr.
965 : 1420 : m_map.put (caller_sval, entry_t (kv.second.m_state, caller_origin));
966 : : }
967 : 9107 : m_global_state = summary.m_global_state;
968 : 9107 : return true;
969 : : }
970 : :
971 : : /* program_state's copy ctor. */
972 : :
973 : 2425937 : program_state::program_state (const program_state &other)
974 : 2425937 : : m_region_model (new region_model (*other.m_region_model)),
975 : 4851874 : m_checker_states (other.m_checker_states.length ()),
976 : 2425937 : m_valid (true)
977 : : {
978 : 2425937 : int i;
979 : 2425937 : sm_state_map *smap;
980 : 19385325 : FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
981 : 16959388 : m_checker_states.quick_push (smap->clone ());
982 : 2425937 : }
983 : :
984 : : /* program_state's assignment operator. */
985 : :
986 : : program_state&
987 : 299214 : program_state::operator= (const program_state &other)
988 : : {
989 : 299214 : delete m_region_model;
990 : 299214 : m_region_model = new region_model (*other.m_region_model);
991 : :
992 : 299214 : int i;
993 : 299214 : sm_state_map *smap;
994 : 2392261 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
995 : 4186094 : delete smap;
996 : 299214 : m_checker_states.truncate (0);
997 : 897642 : gcc_assert (m_checker_states.space (other.m_checker_states.length ()));
998 : :
999 : 2392261 : FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
1000 : 2093047 : m_checker_states.quick_push (smap->clone ());
1001 : :
1002 : 299214 : m_valid = other.m_valid;
1003 : :
1004 : 299214 : return *this;
1005 : : }
1006 : :
1007 : : /* Move constructor for program_state (when building with C++11). */
1008 : 624333 : program_state::program_state (program_state &&other)
1009 : 624333 : : m_region_model (other.m_region_model),
1010 : 1248666 : m_checker_states (other.m_checker_states.length ())
1011 : : {
1012 : 624333 : other.m_region_model = nullptr;
1013 : :
1014 : 624333 : int i;
1015 : 624333 : sm_state_map *smap;
1016 : 4989404 : FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
1017 : 4365071 : m_checker_states.quick_push (smap);
1018 : 624333 : other.m_checker_states.truncate (0);
1019 : :
1020 : 624333 : m_valid = other.m_valid;
1021 : 624333 : }
1022 : :
1023 : : /* program_state's dtor. */
1024 : :
1025 : 3389509 : program_state::~program_state ()
1026 : : {
1027 : 3389509 : delete m_region_model;
1028 : 3389509 : }
1029 : :
1030 : : /* Generate a hash value for this program_state. */
1031 : :
1032 : : hashval_t
1033 : 449104 : program_state::hash () const
1034 : : {
1035 : 449104 : hashval_t result = m_region_model->hash ();
1036 : :
1037 : 449104 : int i;
1038 : 449104 : sm_state_map *smap;
1039 : 4037882 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1040 : 3139674 : result ^= smap->hash ();
1041 : 449104 : return result;
1042 : : }
1043 : :
1044 : : /* Equality operator for program_state.
1045 : : All parts of the program_state (region model, checker states) must
1046 : : equal their counterparts in OTHER for the two program_states to be
1047 : : considered equal. */
1048 : :
1049 : : bool
1050 : 73906 : program_state::operator== (const program_state &other) const
1051 : : {
1052 : 73906 : if (!(*m_region_model == *other.m_region_model))
1053 : : return false;
1054 : :
1055 : : int i;
1056 : : sm_state_map *smap;
1057 : 70153 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1058 : 61657 : if (!(*smap == *other.m_checker_states[i]))
1059 : : return false;
1060 : :
1061 : 8496 : gcc_checking_assert (hash () == other.hash ());
1062 : :
1063 : : return true;
1064 : : }
1065 : :
1066 : : /* Print a compact representation of this state to PP. */
1067 : :
1068 : : void
1069 : 0 : program_state::print (const extrinsic_state &ext_state,
1070 : : pretty_printer *pp) const
1071 : : {
1072 : 0 : pp_printf (pp, "rmodel: ");
1073 : 0 : m_region_model->dump_to_pp (pp, true, false);
1074 : 0 : pp_newline (pp);
1075 : :
1076 : 0 : int i;
1077 : 0 : sm_state_map *smap;
1078 : 0 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1079 : : {
1080 : 0 : if (!smap->is_empty_p ())
1081 : : {
1082 : 0 : pp_printf (pp, "%s: ", ext_state.get_name (i));
1083 : 0 : smap->print (m_region_model, true, false, pp);
1084 : 0 : pp_newline (pp);
1085 : : }
1086 : : }
1087 : 0 : if (!m_valid)
1088 : : {
1089 : 0 : pp_printf (pp, "invalid state");
1090 : 0 : pp_newline (pp);
1091 : : }
1092 : 0 : }
1093 : :
1094 : : /* Dump a representation of this state to PP. */
1095 : :
1096 : : void
1097 : 1581 : program_state::dump_to_pp (const extrinsic_state &ext_state,
1098 : : bool /*summarize*/, bool multiline,
1099 : : pretty_printer *pp) const
1100 : : {
1101 : 1581 : if (!multiline)
1102 : 964 : pp_string (pp, "{");
1103 : 1581 : {
1104 : 1581 : pp_printf (pp, "rmodel:");
1105 : 1581 : if (multiline)
1106 : 617 : pp_newline (pp);
1107 : : else
1108 : 964 : pp_string (pp, " {");
1109 : 1581 : m_region_model->dump_to_pp (pp, true, multiline);
1110 : 1581 : if (!multiline)
1111 : 964 : pp_string (pp, "}");
1112 : : }
1113 : :
1114 : : int i;
1115 : : sm_state_map *smap;
1116 : 12648 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1117 : : {
1118 : 11067 : if (!smap->is_empty_p ())
1119 : : {
1120 : 498 : if (!multiline)
1121 : 98 : pp_string (pp, " {");
1122 : 498 : pp_printf (pp, "%s: ", ext_state.get_name (i));
1123 : 498 : if (multiline)
1124 : 400 : pp_newline (pp);
1125 : 498 : smap->print (m_region_model, true, multiline, pp);
1126 : 498 : if (!multiline)
1127 : 98 : pp_string (pp, "}");
1128 : : }
1129 : : }
1130 : :
1131 : 1581 : if (!m_valid)
1132 : : {
1133 : 0 : if (!multiline)
1134 : 0 : pp_space (pp);
1135 : 0 : pp_printf (pp, "invalid state");
1136 : 0 : if (multiline)
1137 : 0 : pp_newline (pp);
1138 : : }
1139 : 1581 : if (!multiline)
1140 : 964 : pp_string (pp, "}");
1141 : 1581 : }
1142 : :
1143 : : /* Dump a representation of this state to OUTF. */
1144 : :
1145 : : void
1146 : 0 : program_state::dump_to_file (const extrinsic_state &ext_state,
1147 : : bool summarize, bool multiline,
1148 : : FILE *outf) const
1149 : : {
1150 : 0 : tree_dump_pretty_printer pp (outf);
1151 : 0 : dump_to_pp (ext_state, summarize, multiline, &pp);
1152 : 0 : }
1153 : :
1154 : : /* Dump a multiline representation of this state to stderr. */
1155 : :
1156 : : DEBUG_FUNCTION void
1157 : 0 : program_state::dump (const extrinsic_state &ext_state,
1158 : : bool summarize) const
1159 : : {
1160 : 0 : dump_to_file (ext_state, summarize, true, stderr);
1161 : 0 : }
1162 : :
1163 : : /* Dump a tree-like representation of this state to stderr. */
1164 : :
1165 : : DEBUG_FUNCTION void
1166 : 0 : program_state::dump () const
1167 : : {
1168 : 0 : text_art::dump (*this);
1169 : 0 : }
1170 : :
1171 : : /* Return a new json::object of the form
1172 : : {"store" : object for store,
1173 : : "constraints" : object for constraint_manager,
1174 : : "curr_frame" : (optional) str for current frame,
1175 : : "checkers" : { STATE_NAME : object per sm_state_map },
1176 : : "valid" : true/false}. */
1177 : :
1178 : : std::unique_ptr<json::object>
1179 : 0 : program_state::to_json (const extrinsic_state &ext_state) const
1180 : : {
1181 : 0 : auto state_obj = std::make_unique<json::object> ();
1182 : :
1183 : 0 : state_obj->set ("store", m_region_model->get_store ()->to_json ());
1184 : 0 : state_obj->set ("constraints",
1185 : 0 : m_region_model->get_constraints ()->to_json ());
1186 : 0 : if (m_region_model->get_current_frame ())
1187 : 0 : state_obj->set ("curr_frame",
1188 : 0 : m_region_model->get_current_frame ()->to_json ());
1189 : :
1190 : : /* Provide m_checker_states as an object, using names as keys. */
1191 : 0 : {
1192 : 0 : auto checkers_obj = std::make_unique<json::object> ();
1193 : :
1194 : 0 : int i;
1195 : 0 : sm_state_map *smap;
1196 : 0 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1197 : 0 : if (!smap->is_empty_p ())
1198 : 0 : checkers_obj->set (ext_state.get_name (i), smap->to_json ());
1199 : :
1200 : 0 : state_obj->set ("checkers", std::move (checkers_obj));
1201 : 0 : }
1202 : :
1203 : 0 : state_obj->set_bool ("valid", m_valid);
1204 : :
1205 : 0 : return state_obj;
1206 : : }
1207 : :
1208 : :
1209 : : std::unique_ptr<text_art::tree_widget>
1210 : 0 : program_state::make_dump_widget (const text_art::dump_widget_info &dwi) const
1211 : : {
1212 : 0 : using text_art::tree_widget;
1213 : 0 : std::unique_ptr<tree_widget> state_widget
1214 : 0 : (tree_widget::from_fmt (dwi, nullptr, "State"));
1215 : :
1216 : 0 : state_widget->add_child (m_region_model->make_dump_widget (dwi));
1217 : :
1218 : : /* Add nodes for any sm_state_maps with state. */
1219 : 0 : {
1220 : 0 : int i;
1221 : 0 : sm_state_map *smap;
1222 : 0 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1223 : 0 : if (!smap->is_empty_p ())
1224 : 0 : state_widget->add_child (smap->make_dump_widget (dwi, m_region_model));
1225 : : }
1226 : :
1227 : 0 : return state_widget;
1228 : : }
1229 : :
1230 : : void
1231 : 0 : program_state::dump_dot (const extrinsic_state &ext_state) const
1232 : : {
1233 : 0 : auto state_graph = make_diagnostic_state_graph (ext_state);
1234 : :
1235 : 0 : gcc_assert (global_dc);
1236 : 0 : auto logical_loc_mgr = global_dc->get_logical_location_manager ();
1237 : 0 : gcc_assert (logical_loc_mgr);
1238 : :
1239 : 0 : auto graph = diagnostics::state_graphs::make_dot_graph (*state_graph,
1240 : 0 : *logical_loc_mgr);
1241 : :
1242 : 0 : pretty_printer pp;
1243 : 0 : dot::writer w (pp);
1244 : 0 : graph->print (w);
1245 : 0 : pp_flush (&pp);
1246 : 0 : }
1247 : :
1248 : : /* Update this program_state to reflect a top-level call to FUN.
1249 : : The params will have initial_svalues. */
1250 : :
1251 : : void
1252 : 9969 : program_state::push_frame (const extrinsic_state &ext_state ATTRIBUTE_UNUSED,
1253 : : const function &fun)
1254 : : {
1255 : 9969 : m_region_model->push_frame (fun, nullptr, nullptr, nullptr);
1256 : 9969 : }
1257 : :
1258 : : /* Get the current function of this state. */
1259 : :
1260 : : const function *
1261 : 22 : program_state::get_current_function () const
1262 : : {
1263 : 22 : return m_region_model->get_current_function ();
1264 : : }
1265 : :
1266 : : /* Determine if following edge SUCC from ENODE is valid within the graph EG
1267 : : and update this state accordingly in-place.
1268 : :
1269 : : Return true if the edge can be followed, or false otherwise.
1270 : :
1271 : : Check for relevant conditionals and switch-values for conditionals
1272 : : and switch statements, adding the relevant conditions to this state.
1273 : : Push/pop frames for interprocedural edges and update params/returned
1274 : : values.
1275 : :
1276 : : This is the "state" half of exploded_node::on_edge. */
1277 : :
1278 : : bool
1279 : 125788 : program_state::on_edge (exploded_graph &eg,
1280 : : exploded_node *enode,
1281 : : const superedge *succ,
1282 : : uncertainty_t *uncertainty)
1283 : : {
1284 : 251576 : class my_path_context : public path_context
1285 : : {
1286 : : public:
1287 : 125788 : my_path_context (bool &terminated) : m_terminated (terminated) {}
1288 : 0 : void bifurcate (std::unique_ptr<custom_edge_info>) final override
1289 : : {
1290 : 0 : gcc_unreachable ();
1291 : : }
1292 : :
1293 : 28 : void terminate_path () final override
1294 : : {
1295 : 28 : m_terminated = true;
1296 : 28 : }
1297 : :
1298 : 0 : bool terminate_path_p () const final override
1299 : : {
1300 : 0 : return m_terminated;
1301 : : }
1302 : : bool &m_terminated;
1303 : : };
1304 : :
1305 : : /* Update state. */
1306 : 125788 : const program_point &point = enode->get_point ();
1307 : 125788 : const gimple *last_stmt = point.get_supernode ()->get_last_stmt ();
1308 : :
1309 : : /* For conditionals and switch statements, add the
1310 : : relevant conditions (for the specific edge) to new_state;
1311 : : skip edges for which the resulting constraints
1312 : : are impossible.
1313 : : This also updates frame information for call/return superedges.
1314 : : Adding the relevant conditions for the edge could also trigger
1315 : : sm-state transitions (e.g. transitions due to ptrs becoming known
1316 : : to be NULL or non-NULL) */
1317 : 125788 : bool terminated = false;
1318 : 125788 : my_path_context path_ctxt (terminated);
1319 : 125788 : impl_region_model_context ctxt (eg, enode,
1320 : 125788 : &enode->get_state (),
1321 : : this,
1322 : : uncertainty, &path_ctxt,
1323 : 125788 : last_stmt);
1324 : 125788 : std::unique_ptr<rejected_constraint> rc;
1325 : 125788 : logger * const logger = eg.get_logger ();
1326 : 251535 : if (!m_region_model->maybe_update_for_edge (*succ,
1327 : : last_stmt,
1328 : : &ctxt,
1329 : : logger ? &rc : nullptr))
1330 : : {
1331 : 6170 : if (logger)
1332 : : {
1333 : 0 : logger->start_log_line ();
1334 : 0 : logger->log_partial ("edge to SN: %i is impossible"
1335 : : " due to region_model constraint: ",
1336 : 0 : succ->m_dest->m_index);
1337 : 0 : rc->dump_to_pp (logger->get_printer ());
1338 : 0 : logger->end_log_line ();
1339 : : }
1340 : 6170 : return false;
1341 : : }
1342 : 119618 : if (terminated)
1343 : : return false;
1344 : :
1345 : 119590 : program_state::detect_leaks (enode->get_state (), *this,
1346 : : nullptr, eg.get_ext_state (),
1347 : : &ctxt);
1348 : :
1349 : 119590 : return true;
1350 : 125788 : }
1351 : :
1352 : : /* Update this program_state to reflect a call to function
1353 : : represented by CALL_STMT.
1354 : : currently used only when the call doesn't have a superedge representing
1355 : : the call ( like call via a function pointer ) */
1356 : : void
1357 : 77 : program_state::push_call (exploded_graph &eg,
1358 : : exploded_node *enode,
1359 : : const gcall &call_stmt,
1360 : : uncertainty_t *uncertainty)
1361 : : {
1362 : : /* Update state. */
1363 : 77 : const program_point &point = enode->get_point ();
1364 : 77 : const gimple *last_stmt = point.get_supernode ()->get_last_stmt ();
1365 : :
1366 : 77 : impl_region_model_context ctxt (eg, enode,
1367 : 77 : &enode->get_state (),
1368 : : this,
1369 : : uncertainty,
1370 : : nullptr,
1371 : 77 : last_stmt);
1372 : 77 : m_region_model->update_for_gcall (call_stmt, &ctxt);
1373 : 77 : }
1374 : :
1375 : : /* Update this program_state to reflect a return from function
1376 : : call to which is represented by CALL_STMT.
1377 : : currently used only when the call doesn't have a superedge representing
1378 : : the return */
1379 : : void
1380 : 67 : program_state::returning_call (exploded_graph &eg,
1381 : : exploded_node *enode,
1382 : : const gcall &call_stmt,
1383 : : uncertainty_t *uncertainty)
1384 : : {
1385 : : /* Update state. */
1386 : 67 : const program_point &point = enode->get_point ();
1387 : 67 : const gimple *last_stmt = point.get_supernode ()->get_last_stmt ();
1388 : :
1389 : 67 : impl_region_model_context ctxt (eg, enode,
1390 : 67 : &enode->get_state (),
1391 : : this,
1392 : : uncertainty,
1393 : : nullptr,
1394 : 67 : last_stmt);
1395 : 67 : m_region_model->update_for_return_gcall (call_stmt, &ctxt);
1396 : 67 : }
1397 : :
1398 : : /* Generate a simpler version of THIS, discarding state that's no longer
1399 : : relevant at POINT.
1400 : : The idea is that we're more likely to be able to consolidate
1401 : : multiple (point, state) into single exploded_nodes if we discard
1402 : : irrelevant state (e.g. at the end of functions). */
1403 : :
1404 : : program_state
1405 : 627641 : program_state::prune_for_point (exploded_graph &eg,
1406 : : const program_point &point,
1407 : : exploded_node *enode_for_diag,
1408 : : uncertainty_t *uncertainty) const
1409 : : {
1410 : 627641 : logger * const logger = eg.get_logger ();
1411 : 627641 : LOG_SCOPE (logger);
1412 : :
1413 : 627641 : function *fun = point.get_function ();
1414 : 627641 : if (!fun)
1415 : 3308 : return *this;
1416 : :
1417 : 624333 : program_state new_state (*this);
1418 : :
1419 : 624333 : const state_purge_map *pm = eg.get_purge_map ();
1420 : 624333 : if (pm)
1421 : : {
1422 : 623669 : unsigned num_ssas_purged = 0;
1423 : 623669 : unsigned num_decls_purged = 0;
1424 : 623669 : auto_vec<const decl_region *> regs;
1425 : 623669 : new_state.m_region_model->get_regions_for_current_frame (®s);
1426 : 623669 : regs.qsort (region::cmp_ptr_ptr);
1427 : : unsigned i;
1428 : : const decl_region *reg;
1429 : 1966834 : FOR_EACH_VEC_ELT (regs, i, reg)
1430 : : {
1431 : 1343165 : const tree node = reg->get_decl ();
1432 : 1343165 : if (TREE_CODE (node) == SSA_NAME)
1433 : : {
1434 : 1130411 : const tree ssa_name = node;
1435 : 1130411 : const state_purge_per_ssa_name &per_ssa
1436 : 1130411 : = pm->get_data_for_ssa_name (node);
1437 : 1130411 : if (!per_ssa.needed_at_point_p (point.get_function_point ()))
1438 : : {
1439 : : /* Don't purge bindings of SSA names to svalues
1440 : : that have unpurgable sm-state, so that leaks are
1441 : : reported at the end of the function, rather than
1442 : : at the last place that such an SSA name is referred to.
1443 : :
1444 : : But do purge them for temporaries (when SSA_NAME_VAR is
1445 : : NULL), so that we report for cases where a leak happens when
1446 : : a variable is overwritten with another value, so that the leak
1447 : : is reported at the point of overwrite, rather than having
1448 : : temporaries keep the value reachable until the frame is
1449 : : popped. */
1450 : 209313 : const svalue *sval
1451 : 209313 : = new_state.m_region_model->get_store_value (reg, nullptr);
1452 : 209313 : if (!new_state.can_purge_p (eg.get_ext_state (), sval)
1453 : 253037 : && SSA_NAME_VAR (ssa_name))
1454 : : {
1455 : : /* (currently only state maps can keep things
1456 : : alive). */
1457 : 36818 : if (logger)
1458 : 0 : logger->log ("not purging binding for %qE"
1459 : : " (used by state map)", ssa_name);
1460 : 36818 : continue;
1461 : : }
1462 : :
1463 : 172495 : new_state.m_region_model->purge_region (reg);
1464 : 172495 : num_ssas_purged++;
1465 : : }
1466 : : }
1467 : : else
1468 : : {
1469 : 212754 : const tree decl = node;
1470 : 212754 : gcc_assert (TREE_CODE (node) == VAR_DECL
1471 : : || TREE_CODE (node) == PARM_DECL
1472 : : || TREE_CODE (node) == RESULT_DECL);
1473 : 425508 : if (const state_purge_per_decl *per_decl
1474 : 212754 : = pm->get_any_data_for_decl (decl))
1475 : 165645 : if (!per_decl->needed_at_point_p (point.get_function_point ()))
1476 : : {
1477 : : /* Don't purge bindings of decls if there are svalues
1478 : : that have unpurgable sm-state within the decl's cluster,
1479 : : so that leaks are reported at the end of the function,
1480 : : rather than at the last place that such a decl is
1481 : : referred to. */
1482 : 5210 : if (!new_state.can_purge_base_region_p (eg.get_ext_state (),
1483 : : reg))
1484 : : {
1485 : : /* (currently only state maps can keep things
1486 : : alive). */
1487 : 1382 : if (logger)
1488 : 0 : logger->log ("not purging binding for %qE"
1489 : : " (value in binding used by state map)",
1490 : : decl);
1491 : 1382 : continue;
1492 : : }
1493 : :
1494 : 3828 : new_state.m_region_model->purge_region (reg);
1495 : 3828 : num_decls_purged++;
1496 : : }
1497 : : }
1498 : : }
1499 : :
1500 : 623669 : if (num_ssas_purged > 0 || num_decls_purged > 0)
1501 : : {
1502 : 141627 : if (logger)
1503 : : {
1504 : 77 : logger->log ("num_ssas_purged: %i", num_ssas_purged);
1505 : 77 : logger->log ("num_decl_purged: %i", num_decls_purged);
1506 : : }
1507 : 141627 : impl_region_model_context ctxt (eg, enode_for_diag,
1508 : : this,
1509 : : &new_state,
1510 : : uncertainty, nullptr,
1511 : 141627 : point.get_stmt ());
1512 : 141627 : detect_leaks (*this, new_state, nullptr, eg.get_ext_state (), &ctxt);
1513 : 141627 : }
1514 : 623669 : }
1515 : :
1516 : 624333 : new_state.m_region_model->canonicalize ();
1517 : :
1518 : 624333 : return new_state;
1519 : 627641 : }
1520 : :
1521 : : /* Return true if there are no unpurgeable bindings within BASE_REG. */
1522 : :
1523 : : bool
1524 : 5210 : program_state::can_purge_base_region_p (const extrinsic_state &ext_state,
1525 : : const region *base_reg) const
1526 : : {
1527 : 5210 : binding_cluster *cluster
1528 : 5210 : = m_region_model->get_store ()->get_cluster (base_reg);
1529 : 5210 : if (!cluster)
1530 : : return true;
1531 : :
1532 : 20660 : for (auto iter : *cluster)
1533 : : {
1534 : 9107 : const svalue *sval = iter.second;
1535 : 9107 : if (!can_purge_p (ext_state, sval))
1536 : 1382 : return false;
1537 : : }
1538 : :
1539 : 3828 : return true;
1540 : : }
1541 : :
1542 : : /* Get a representative tree to use for describing SVAL. */
1543 : :
1544 : : tree
1545 : 0 : program_state::get_representative_tree (const svalue *sval) const
1546 : : {
1547 : 0 : gcc_assert (m_region_model);
1548 : 0 : return m_region_model->get_representative_tree (sval);
1549 : : }
1550 : :
1551 : : /* Attempt to merge this state with OTHER, both at POINT.
1552 : : Write the result to *OUT.
1553 : : If the states were merged successfully, return true. */
1554 : :
1555 : : bool
1556 : 325932 : program_state::can_merge_with_p (const program_state &other,
1557 : : const extrinsic_state &ext_state,
1558 : : const program_point &point,
1559 : : program_state *out) const
1560 : : {
1561 : 325932 : gcc_assert (out);
1562 : 325932 : gcc_assert (m_region_model);
1563 : :
1564 : : /* Attempt to merge the sm-states. */
1565 : : int i;
1566 : : sm_state_map *smap;
1567 : 1531497 : FOR_EACH_VEC_ELT (out->m_checker_states, i, smap)
1568 : 2730254 : if (!m_checker_states[i]->can_merge_with_p (*other.m_checker_states[i],
1569 : : ext_state.get_sm (i),
1570 : : ext_state,
1571 : 1365127 : &out->m_checker_states[i]))
1572 : : return false;
1573 : :
1574 : : /* Attempt to merge the region_models. */
1575 : 166370 : if (!m_region_model->can_merge_with_p (*other.m_region_model,
1576 : : point,
1577 : : out->m_region_model,
1578 : : &ext_state,
1579 : : this, &other))
1580 : : return false;
1581 : :
1582 : 57979 : out->m_region_model->canonicalize ();
1583 : :
1584 : 57979 : return true;
1585 : : }
1586 : :
1587 : : /* Assert that this object is valid. */
1588 : :
1589 : : void
1590 : 1724337 : program_state::validate (const extrinsic_state &ext_state) const
1591 : : {
1592 : : /* Skip this in a release build. */
1593 : : #if !CHECKING_P
1594 : : return;
1595 : : #endif
1596 : :
1597 : 3448674 : gcc_assert (m_checker_states.length () == ext_state.get_num_checkers ());
1598 : 1724337 : m_region_model->validate ();
1599 : 1724337 : }
1600 : :
1601 : : static void
1602 : 496 : log_set_of_svalues (logger *logger, const char *name,
1603 : : const svalue_set &set)
1604 : : {
1605 : 496 : logger->log (name);
1606 : 496 : logger->inc_indent ();
1607 : 496 : auto_vec<const svalue *> sval_vecs (set.elements ());
1608 : 496 : for (svalue_set::iterator iter = set.begin ();
1609 : 4556 : iter != set.end (); ++iter)
1610 : 2030 : sval_vecs.quick_push (*iter);
1611 : 496 : sval_vecs.qsort (svalue::cmp_ptr_ptr);
1612 : : unsigned i;
1613 : : const svalue *sval;
1614 : 2526 : FOR_EACH_VEC_ELT (sval_vecs, i, sval)
1615 : : {
1616 : 2030 : logger->start_log_line ();
1617 : 2030 : pretty_printer *pp = logger->get_printer ();
1618 : 2030 : if (!flag_dump_noaddr)
1619 : : {
1620 : 2030 : pp_pointer (pp, sval);
1621 : 2030 : pp_string (pp, ": ");
1622 : : }
1623 : 2030 : sval->dump_to_pp (pp, false);
1624 : 2030 : logger->end_log_line ();
1625 : : }
1626 : 496 : logger->dec_indent ();
1627 : 496 : }
1628 : :
1629 : : /* Compare the sets of svalues reachable from each of SRC_STATE and DEST_STATE.
1630 : : For all svalues that are reachable in SRC_STATE and are not live in
1631 : : DEST_STATE (whether explicitly reachable in DEST_STATE, or implicitly live
1632 : : based on the former set), call CTXT->on_svalue_leak for them.
1633 : :
1634 : : Call on_liveness_change on both the CTXT and on the DEST_STATE's
1635 : : constraint_manager, purging dead svalues from sm-state and from
1636 : : constraints, respectively.
1637 : :
1638 : : This function should be called at each fine-grained state change, not
1639 : : just at exploded edges. */
1640 : :
1641 : : void
1642 : 588961 : program_state::detect_leaks (const program_state &src_state,
1643 : : const program_state &dest_state,
1644 : : const svalue *extra_sval,
1645 : : const extrinsic_state &ext_state,
1646 : : region_model_context *ctxt)
1647 : : {
1648 : 588961 : logger *logger = ext_state.get_logger ();
1649 : 588961 : LOG_SCOPE (logger);
1650 : 588961 : const uncertainty_t *uncertainty = ctxt->get_uncertainty ();
1651 : 588961 : if (logger)
1652 : : {
1653 : 248 : pretty_printer *pp = logger->get_printer ();
1654 : 248 : logger->start_log_line ();
1655 : 248 : pp_string (pp, "src_state: ");
1656 : 248 : src_state.dump_to_pp (ext_state, true, false, pp);
1657 : 248 : logger->end_log_line ();
1658 : 248 : logger->start_log_line ();
1659 : 248 : pp_string (pp, "dest_state: ");
1660 : 248 : dest_state.dump_to_pp (ext_state, true, false, pp);
1661 : 248 : logger->end_log_line ();
1662 : 248 : if (extra_sval)
1663 : : {
1664 : 0 : logger->start_log_line ();
1665 : 0 : pp_string (pp, "extra_sval: ");
1666 : 0 : extra_sval->dump_to_pp (pp, true);
1667 : 0 : logger->end_log_line ();
1668 : : }
1669 : 248 : if (uncertainty)
1670 : : {
1671 : 248 : logger->start_log_line ();
1672 : 248 : pp_string (pp, "uncertainty: ");
1673 : 248 : uncertainty->dump_to_pp (pp, true);
1674 : 248 : logger->end_log_line ();
1675 : : }
1676 : : }
1677 : :
1678 : : /* Get svalues reachable from each of src_state and dest_state.
1679 : : Get svalues *known* to be reachable in src_state.
1680 : : Pass in uncertainty for dest_state so that we additionally get svalues that
1681 : : *might* still be reachable in dst_state. */
1682 : 588961 : svalue_set known_src_svalues;
1683 : 588961 : src_state.m_region_model->get_reachable_svalues (&known_src_svalues,
1684 : : nullptr, nullptr);
1685 : 588961 : svalue_set maybe_dest_svalues;
1686 : 588961 : dest_state.m_region_model->get_reachable_svalues (&maybe_dest_svalues,
1687 : : extra_sval, uncertainty);
1688 : :
1689 : 588961 : if (logger)
1690 : : {
1691 : 248 : log_set_of_svalues (logger, "src_state known reachable svalues:",
1692 : : known_src_svalues);
1693 : 248 : log_set_of_svalues (logger, "dest_state maybe reachable svalues:",
1694 : : maybe_dest_svalues);
1695 : : }
1696 : :
1697 : 588961 : auto_vec <const svalue *> dead_svals (known_src_svalues.elements ());
1698 : 3627625 : for (svalue_set::iterator iter = known_src_svalues.begin ();
1699 : 6666289 : iter != known_src_svalues.end (); ++iter)
1700 : : {
1701 : 3038664 : const svalue *sval = (*iter);
1702 : : /* For each sval reachable from SRC_STATE, determine if it is
1703 : : live in DEST_STATE: either explicitly reachable, implicitly
1704 : : live based on the set of explicitly reachable svalues,
1705 : : or possibly reachable as recorded in uncertainty.
1706 : : Record those that have ceased to be live i.e. were known
1707 : : to be live, and are now not known to be even possibly-live. */
1708 : 3038664 : if (!sval->live_p (&maybe_dest_svalues, dest_state.m_region_model))
1709 : 75298 : dead_svals.quick_push (sval);
1710 : : }
1711 : :
1712 : : /* Call CTXT->on_svalue_leak on all svals in SRC_STATE that have ceased
1713 : : to be live, sorting them first to ensure deterministic behavior. */
1714 : 588961 : dead_svals.qsort (svalue::cmp_ptr_ptr);
1715 : : unsigned i;
1716 : : const svalue *sval;
1717 : 664259 : FOR_EACH_VEC_ELT (dead_svals, i, sval)
1718 : 75298 : ctxt->on_svalue_leak (sval);
1719 : :
1720 : : /* Purge dead svals from sm-state. */
1721 : 588961 : ctxt->on_liveness_change (maybe_dest_svalues,
1722 : 588961 : dest_state.m_region_model);
1723 : :
1724 : : /* Purge dead svals from constraints. */
1725 : 588961 : dest_state.m_region_model->get_constraints ()->on_liveness_change
1726 : 588961 : (maybe_dest_svalues, dest_state.m_region_model);
1727 : :
1728 : : /* Purge dead heap-allocated regions from dynamic extents. */
1729 : 1680791 : for (const svalue *sval : dead_svals)
1730 : 75298 : if (const region *reg = sval->maybe_get_region ())
1731 : 12069 : if (reg->get_kind () == RK_HEAP_ALLOCATED)
1732 : 6837 : dest_state.m_region_model->unset_dynamic_extents (reg);
1733 : 588961 : }
1734 : :
1735 : : /* Attempt to use R to replay SUMMARY into this object.
1736 : : Return true if it is possible. */
1737 : :
1738 : : bool
1739 : 1386 : program_state::replay_call_summary (call_summary_replay &r,
1740 : : const program_state &summary)
1741 : : {
1742 : 1386 : if (!m_region_model->replay_call_summary (r, *summary.m_region_model))
1743 : : return false;
1744 : :
1745 : 10408 : for (unsigned sm_idx = 0; sm_idx < m_checker_states.length (); sm_idx++)
1746 : : {
1747 : 9107 : const sm_state_map *summary_sm_map = summary.m_checker_states[sm_idx];
1748 : 9107 : m_checker_states[sm_idx]->replay_call_summary (r, *summary_sm_map);
1749 : : }
1750 : :
1751 : 1301 : if (!summary.m_valid)
1752 : 0 : m_valid = false;
1753 : :
1754 : : return true;
1755 : : }
1756 : :
1757 : : /* Handle calls to "__analyzer_dump_state". */
1758 : :
1759 : : void
1760 : 361 : program_state::impl_call_analyzer_dump_state (const gcall &call,
1761 : : const extrinsic_state &ext_state,
1762 : : region_model_context *ctxt)
1763 : : {
1764 : 361 : call_details cd (call, m_region_model, ctxt);
1765 : 361 : const char *sm_name = cd.get_arg_string_literal (0);
1766 : 361 : if (!sm_name)
1767 : : {
1768 : 4 : error_at (call.location, "cannot determine state machine");
1769 : 16 : return;
1770 : : }
1771 : 357 : unsigned sm_idx;
1772 : 357 : if (!ext_state.get_sm_idx_by_name (sm_name, &sm_idx))
1773 : : {
1774 : 8 : error_at (call.location, "unrecognized state machine %qs", sm_name);
1775 : 8 : return;
1776 : : }
1777 : 349 : const sm_state_map *smap = m_checker_states[sm_idx];
1778 : :
1779 : 349 : const svalue *sval = cd.get_arg_svalue (1);
1780 : :
1781 : : /* Strip off cast to int (due to variadic args). */
1782 : 349 : if (const svalue *cast = sval->maybe_undo_cast ())
1783 : 5 : sval = cast;
1784 : :
1785 : 349 : state_machine::state_t state = smap->get_state (sval, ext_state);
1786 : 349 : warning_at (call.location, 0, "state: %qs", state->get_name ());
1787 : : }
1788 : :
1789 : : #if CHECKING_P
1790 : :
1791 : : namespace selftest {
1792 : :
1793 : : /* Tests for sm_state_map. */
1794 : :
1795 : : static void
1796 : 4 : test_sm_state_map ()
1797 : : {
1798 : 4 : tree x = build_global_decl ("x", integer_type_node);
1799 : 4 : tree y = build_global_decl ("y", integer_type_node);
1800 : 4 : tree z = build_global_decl ("z", integer_type_node);
1801 : :
1802 : 4 : std::unique_ptr<state_machine> sm = make_malloc_state_machine (nullptr);
1803 : 4 : state_machine::state_t start = sm->get_start_state ();
1804 : 4 : std::vector<std::unique_ptr<state_machine>> checkers;
1805 : 4 : const state_machine &borrowed_sm = *sm.get ();
1806 : 4 : checkers.push_back (std::move (sm));
1807 : 4 : engine eng;
1808 : 4 : extrinsic_state ext_state (std::move (checkers), &eng);
1809 : :
1810 : : /* Test setting states on svalue_id instances directly. */
1811 : 4 : {
1812 : 4 : const state_machine::state test_state_42 ("test state 42", 42);
1813 : 4 : const state_machine::state_t TEST_STATE_42 = &test_state_42;
1814 : 4 : region_model_manager mgr;
1815 : 4 : region_model model (&mgr);
1816 : 4 : const svalue *x_sval = model.get_rvalue (x, nullptr);
1817 : 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1818 : 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1819 : :
1820 : 4 : sm_state_map map (borrowed_sm);
1821 : 4 : ASSERT_TRUE (map.is_empty_p ());
1822 : 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), start);
1823 : :
1824 : 4 : map.impl_set_state (x_sval, TEST_STATE_42, z_sval, ext_state);
1825 : 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), TEST_STATE_42);
1826 : 4 : ASSERT_EQ (map.get_origin (x_sval, ext_state), z_sval);
1827 : 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), start);
1828 : 4 : ASSERT_FALSE (map.is_empty_p ());
1829 : :
1830 : 4 : map.impl_set_state (y_sval, 0, z_sval, ext_state);
1831 : 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), start);
1832 : :
1833 : 4 : map.impl_set_state (x_sval, 0, z_sval, ext_state);
1834 : 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), start);
1835 : 4 : ASSERT_TRUE (map.is_empty_p ());
1836 : 4 : }
1837 : :
1838 : 4 : const state_machine::state test_state_5 ("test state 5", 5);
1839 : 4 : const state_machine::state_t TEST_STATE_5 = &test_state_5;
1840 : :
1841 : : /* Test setting states via equivalence classes. */
1842 : 4 : {
1843 : 4 : region_model_manager mgr;
1844 : 4 : region_model model (&mgr);
1845 : 4 : const svalue *x_sval = model.get_rvalue (x, nullptr);
1846 : 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1847 : 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1848 : :
1849 : 4 : sm_state_map map (borrowed_sm);
1850 : 4 : ASSERT_TRUE (map.is_empty_p ());
1851 : 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), start);
1852 : 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), start);
1853 : :
1854 : 4 : model.add_constraint (x, EQ_EXPR, y, nullptr);
1855 : :
1856 : : /* Setting x to a state should also update y, as they
1857 : : are in the same equivalence class. */
1858 : 4 : map.set_state (&model, x_sval, TEST_STATE_5, z_sval, ext_state);
1859 : 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), TEST_STATE_5);
1860 : 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), TEST_STATE_5);
1861 : 4 : ASSERT_EQ (map.get_origin (x_sval, ext_state), z_sval);
1862 : 4 : ASSERT_EQ (map.get_origin (y_sval, ext_state), z_sval);
1863 : 4 : }
1864 : :
1865 : : /* Test equality and hashing. */
1866 : 4 : {
1867 : 4 : region_model_manager mgr;
1868 : 4 : region_model model (&mgr);
1869 : 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1870 : 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1871 : :
1872 : 4 : sm_state_map map0 (borrowed_sm);
1873 : 4 : sm_state_map map1 (borrowed_sm);
1874 : 4 : sm_state_map map2 (borrowed_sm);
1875 : :
1876 : 4 : ASSERT_EQ (map0.hash (), map1.hash ());
1877 : 4 : ASSERT_EQ (map0, map1);
1878 : :
1879 : 4 : map1.impl_set_state (y_sval, TEST_STATE_5, z_sval, ext_state);
1880 : 4 : ASSERT_NE (map0.hash (), map1.hash ());
1881 : 4 : ASSERT_NE (map0, map1);
1882 : :
1883 : : /* Make the same change to map2. */
1884 : 4 : map2.impl_set_state (y_sval, TEST_STATE_5, z_sval, ext_state);
1885 : 4 : ASSERT_EQ (map1.hash (), map2.hash ());
1886 : 4 : ASSERT_EQ (map1, map2);
1887 : 4 : }
1888 : :
1889 : : /* Equality and hashing shouldn't depend on ordering. */
1890 : 4 : {
1891 : 4 : const state_machine::state test_state_2 ("test state 2", 2);
1892 : 4 : const state_machine::state_t TEST_STATE_2 = &test_state_2;
1893 : 4 : const state_machine::state test_state_3 ("test state 3", 3);
1894 : 4 : const state_machine::state_t TEST_STATE_3 = &test_state_3;
1895 : 4 : sm_state_map map0 (borrowed_sm);
1896 : 4 : sm_state_map map1 (borrowed_sm);
1897 : 4 : sm_state_map map2 (borrowed_sm);
1898 : :
1899 : 4 : ASSERT_EQ (map0.hash (), map1.hash ());
1900 : 4 : ASSERT_EQ (map0, map1);
1901 : :
1902 : 4 : region_model_manager mgr;
1903 : 4 : region_model model (&mgr);
1904 : 4 : const svalue *x_sval = model.get_rvalue (x, nullptr);
1905 : 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1906 : 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1907 : :
1908 : 4 : map1.impl_set_state (x_sval, TEST_STATE_2, nullptr, ext_state);
1909 : 4 : map1.impl_set_state (y_sval, TEST_STATE_3, nullptr, ext_state);
1910 : 4 : map1.impl_set_state (z_sval, TEST_STATE_2, nullptr, ext_state);
1911 : :
1912 : 4 : map2.impl_set_state (z_sval, TEST_STATE_2, nullptr, ext_state);
1913 : 4 : map2.impl_set_state (y_sval, TEST_STATE_3, nullptr, ext_state);
1914 : 4 : map2.impl_set_state (x_sval, TEST_STATE_2, nullptr, ext_state);
1915 : :
1916 : 4 : ASSERT_EQ (map1.hash (), map2.hash ());
1917 : 4 : ASSERT_EQ (map1, map2);
1918 : 4 : }
1919 : :
1920 : : // TODO: coverage for purging
1921 : 4 : }
1922 : :
1923 : : /* Check program_state works as expected. */
1924 : :
1925 : : static void
1926 : 4 : test_program_state_1 ()
1927 : : {
1928 : : /* Create a program_state for a global ptr "p" that has
1929 : : malloc sm-state, pointing to a region on the heap. */
1930 : 4 : tree p = build_global_decl ("p", ptr_type_node);
1931 : :
1932 : 4 : std::unique_ptr<state_machine> sm = make_malloc_state_machine (nullptr);
1933 : 4 : const state_machine::state_t UNCHECKED_STATE
1934 : 4 : = sm->get_state_by_name ("unchecked");
1935 : :
1936 : 4 : engine eng;
1937 : 4 : extrinsic_state ext_state (std::move (sm), &eng);
1938 : 4 : region_model_manager *mgr = eng.get_model_manager ();
1939 : 4 : program_state s (ext_state);
1940 : 4 : region_model *model = s.m_region_model;
1941 : 4 : const svalue *size_in_bytes
1942 : 4 : = mgr->get_or_create_unknown_svalue (size_type_node);
1943 : 4 : const region *new_reg
1944 : 4 : = model->get_or_create_region_for_heap_alloc (size_in_bytes, nullptr);
1945 : 4 : const svalue *ptr_sval = mgr->get_ptr_svalue (ptr_type_node, new_reg);
1946 : 4 : model->set_value (model->get_lvalue (p, nullptr),
1947 : : ptr_sval, nullptr);
1948 : 4 : sm_state_map *smap = s.m_checker_states[0];
1949 : :
1950 : 4 : smap->impl_set_state (ptr_sval, UNCHECKED_STATE, nullptr, ext_state);
1951 : 4 : ASSERT_EQ (smap->get_state (ptr_sval, ext_state), UNCHECKED_STATE);
1952 : 4 : }
1953 : :
1954 : : /* Check that program_state works for string literals. */
1955 : :
1956 : : static void
1957 : 4 : test_program_state_2 ()
1958 : : {
1959 : : /* Create a program_state for a global ptr "p" that points to
1960 : : a string constant. */
1961 : 4 : tree p = build_global_decl ("p", ptr_type_node);
1962 : :
1963 : 4 : tree string_cst_ptr = build_string_literal (4, "foo");
1964 : :
1965 : 4 : std::vector<std::unique_ptr<state_machine>> checkers;
1966 : 4 : engine eng;
1967 : 4 : extrinsic_state ext_state (std::move (checkers), &eng);
1968 : :
1969 : 4 : program_state s (ext_state);
1970 : 4 : region_model *model = s.m_region_model;
1971 : 4 : const region *p_reg = model->get_lvalue (p, nullptr);
1972 : 4 : const svalue *str_sval = model->get_rvalue (string_cst_ptr, nullptr);
1973 : 4 : model->set_value (p_reg, str_sval, nullptr);
1974 : 4 : }
1975 : :
1976 : : /* Verify that program_states with identical sm-state can be merged,
1977 : : and that the merged program_state preserves the sm-state. */
1978 : :
1979 : : static void
1980 : 4 : test_program_state_merging ()
1981 : : {
1982 : : /* Create a program_state for a global ptr "p" that has
1983 : : malloc sm-state, pointing to a region on the heap. */
1984 : 4 : tree p = build_global_decl ("p", ptr_type_node);
1985 : :
1986 : 4 : engine eng;
1987 : 4 : region_model_manager *mgr = eng.get_model_manager ();
1988 : 4 : program_point point (program_point::origin (*mgr));
1989 : 4 : extrinsic_state ext_state (make_malloc_state_machine (nullptr),
1990 : 4 : &eng);
1991 : :
1992 : 4 : program_state s0 (ext_state);
1993 : 4 : uncertainty_t uncertainty;
1994 : 4 : impl_region_model_context ctxt (&s0, ext_state, &uncertainty);
1995 : :
1996 : 4 : region_model *model0 = s0.m_region_model;
1997 : 4 : const svalue *size_in_bytes
1998 : 4 : = mgr->get_or_create_unknown_svalue (size_type_node);
1999 : 4 : const region *new_reg
2000 : 4 : = model0->get_or_create_region_for_heap_alloc (size_in_bytes, nullptr);
2001 : 4 : const svalue *ptr_sval = mgr->get_ptr_svalue (ptr_type_node, new_reg);
2002 : 4 : model0->set_value (model0->get_lvalue (p, &ctxt),
2003 : : ptr_sval, &ctxt);
2004 : 4 : sm_state_map *smap = s0.m_checker_states[0];
2005 : 4 : const state_machine::state test_state ("test state", 0);
2006 : 4 : const state_machine::state_t TEST_STATE = &test_state;
2007 : 4 : smap->impl_set_state (ptr_sval, TEST_STATE, nullptr, ext_state);
2008 : 4 : ASSERT_EQ (smap->get_state (ptr_sval, ext_state), TEST_STATE);
2009 : :
2010 : 4 : model0->canonicalize ();
2011 : :
2012 : : /* Verify that canonicalization preserves sm-state. */
2013 : 4 : ASSERT_EQ (smap->get_state (model0->get_rvalue (p, nullptr), ext_state),
2014 : : TEST_STATE);
2015 : :
2016 : : /* Make a copy of the program_state. */
2017 : 4 : program_state s1 (s0);
2018 : 4 : ASSERT_EQ (s0, s1);
2019 : :
2020 : : /* We have two identical states with "p" pointing to a heap region
2021 : : with the given sm-state.
2022 : : They ought to be mergeable, preserving the sm-state. */
2023 : 4 : program_state merged (ext_state);
2024 : 4 : ASSERT_TRUE (s0.can_merge_with_p (s1, ext_state, point, &merged));
2025 : 4 : merged.validate (ext_state);
2026 : :
2027 : : /* Verify that the merged state has the sm-state for "p". */
2028 : 4 : region_model *merged_model = merged.m_region_model;
2029 : 4 : sm_state_map *merged_smap = merged.m_checker_states[0];
2030 : 4 : ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, nullptr),
2031 : : ext_state),
2032 : : TEST_STATE);
2033 : :
2034 : : /* Try canonicalizing. */
2035 : 4 : merged.m_region_model->canonicalize ();
2036 : 4 : merged.validate (ext_state);
2037 : :
2038 : : /* Verify that the merged state still has the sm-state for "p". */
2039 : 4 : ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, nullptr),
2040 : : ext_state),
2041 : : TEST_STATE);
2042 : :
2043 : : /* After canonicalization, we ought to have equality with the inputs. */
2044 : 4 : ASSERT_EQ (s0, merged);
2045 : 8 : }
2046 : :
2047 : : /* Verify that program_states with different global-state in an sm-state
2048 : : can't be merged. */
2049 : :
2050 : : static void
2051 : 4 : test_program_state_merging_2 ()
2052 : : {
2053 : 4 : engine eng;
2054 : 4 : region_model_manager *mgr = eng.get_model_manager ();
2055 : 4 : program_point point (program_point::origin (*mgr));
2056 : 4 : extrinsic_state ext_state (make_signal_state_machine (nullptr), &eng);
2057 : :
2058 : 4 : const state_machine::state test_state_0 ("test state 0", 0);
2059 : 4 : const state_machine::state test_state_1 ("test state 1", 1);
2060 : 4 : const state_machine::state_t TEST_STATE_0 = &test_state_0;
2061 : 4 : const state_machine::state_t TEST_STATE_1 = &test_state_1;
2062 : :
2063 : 4 : program_state s0 (ext_state);
2064 : 4 : {
2065 : 4 : sm_state_map *smap0 = s0.m_checker_states[0];
2066 : 4 : smap0->set_global_state (TEST_STATE_0);
2067 : 4 : ASSERT_EQ (smap0->get_global_state (), TEST_STATE_0);
2068 : : }
2069 : :
2070 : 4 : program_state s1 (ext_state);
2071 : 4 : {
2072 : 4 : sm_state_map *smap1 = s1.m_checker_states[0];
2073 : 4 : smap1->set_global_state (TEST_STATE_1);
2074 : 4 : ASSERT_EQ (smap1->get_global_state (), TEST_STATE_1);
2075 : : }
2076 : :
2077 : 4 : ASSERT_NE (s0, s1);
2078 : :
2079 : : /* They ought to not be mergeable. */
2080 : 4 : program_state merged (ext_state);
2081 : 4 : ASSERT_FALSE (s0.can_merge_with_p (s1, ext_state, point, &merged));
2082 : 4 : }
2083 : :
2084 : : /* Run all of the selftests within this file. */
2085 : :
2086 : : void
2087 : 4 : analyzer_program_state_cc_tests ()
2088 : : {
2089 : 4 : test_sm_state_map ();
2090 : 4 : test_program_state_1 ();
2091 : 4 : test_program_state_2 ();
2092 : 4 : test_program_state_merging ();
2093 : 4 : test_program_state_merging_2 ();
2094 : 4 : }
2095 : :
2096 : : } // namespace selftest
2097 : :
2098 : : #endif /* CHECKING_P */
2099 : :
2100 : : } // namespace ana
2101 : :
2102 : : #endif /* #if ENABLE_ANALYZER */
|
