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