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