1 /* Classes for representing the state of interest at a given path of analysis.
2 Copyright (C) 2019-2020 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 #include "system.h"
23 #include "coretypes.h"
24 #include "tree.h"
25 #include "diagnostic-core.h"
26 #include "diagnostic.h"
27 #include "function.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 "tristate.h"
34 #include "ordered-hash-map.h"
35 #include "selftest.h"
36 #include "analyzer/region-model.h"
37 #include "analyzer/program-state.h"
38 #include "analyzer/constraint-manager.h"
39 #include "alloc-pool.h"
40 #include "fibonacci_heap.h"
41 #include "shortest-paths.h"
42 #include "analyzer/constraint-manager.h"
43 #include "diagnostic-event-id.h"
44 #include "analyzer/pending-diagnostic.h"
45 #include "analyzer/diagnostic-manager.h"
46 #include "cfg.h"
47 #include "basic-block.h"
48 #include "gimple.h"
49 #include "gimple-iterator.h"
50 #include "cgraph.h"
51 #include "digraph.h"
52 #include "analyzer/supergraph.h"
53 #include "analyzer/call-string.h"
54 #include "analyzer/program-point.h"
55 #include "analyzer/program-state.h"
56 #include "analyzer/exploded-graph.h"
57 #include "analyzer/state-purge.h"
58 #include "analyzer/analyzer-selftests.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
dump_to_pp(pretty_printer * pp) const69 extrinsic_state::dump_to_pp (pretty_printer *pp) const
70 {
71 pp_printf (pp, "extrinsic_state: %i checker(s)\n", get_num_checkers ());
72 unsigned i;
73 state_machine *checker;
74 FOR_EACH_VEC_ELT (m_checkers, i, checker)
75 {
76 pp_printf (pp, "m_checkers[%i]: %qs\n", i, checker->get_name ());
77 checker->dump_to_pp (pp);
78 }
79 }
80
81 /* Dump a multiline representation of this state to OUTF. */
82
83 void
dump_to_file(FILE * outf) const84 extrinsic_state::dump_to_file (FILE *outf) const
85 {
86 pretty_printer pp;
87 if (outf == stderr)
88 pp_show_color (&pp) = pp_show_color (global_dc->printer);
89 pp.buffer->stream = outf;
90 dump_to_pp (&pp);
91 pp_flush (&pp);
92 }
93
94 /* Dump a multiline representation of this state to stderr. */
95
96 DEBUG_FUNCTION void
dump() const97 extrinsic_state::dump () const
98 {
99 dump_to_file (stderr);
100 }
101
102 /* class sm_state_map. */
103
104 /* sm_state_map's ctor. */
105
sm_state_map()106 sm_state_map::sm_state_map ()
107 : m_map (), m_global_state (0)
108 {
109 }
110
111 /* Clone the sm_state_map. */
112
113 sm_state_map *
clone() const114 sm_state_map::clone () const
115 {
116 return new sm_state_map (*this);
117 }
118
119 /* Clone this sm_state_map, remapping all svalue_ids within it with ID_MAP.
120
121 Return NULL if there are any svalue_ids that have sm-state for which
122 ID_MAP maps them to svalue_id::null (and thus the clone would have lost
123 the sm-state information). */
124
125 sm_state_map *
clone_with_remapping(const one_way_svalue_id_map & id_map) const126 sm_state_map::clone_with_remapping (const one_way_svalue_id_map &id_map) const
127 {
128 sm_state_map *result = new sm_state_map ();
129 result->m_global_state = m_global_state;
130 for (map_t::iterator iter = m_map.begin ();
131 iter != m_map.end ();
132 ++iter)
133 {
134 svalue_id sid = (*iter).first;
135 gcc_assert (!sid.null_p ());
136 entry_t e = (*iter).second;
137 /* TODO: what should we do if the origin maps from non-null to null?
138 Is that loss of information acceptable? */
139 id_map.update (&e.m_origin);
140
141 svalue_id new_sid = id_map.get_dst_for_src (sid);
142 if (new_sid.null_p ())
143 {
144 delete result;
145 return NULL;
146 }
147 result->m_map.put (new_sid, e);
148 }
149 return result;
150 }
151
152 /* Print this sm_state_map (for SM) to PP.
153 If MODEL is non-NULL, print representative tree values where
154 available. */
155
156 void
print(const state_machine & sm,const region_model * model,pretty_printer * pp) const157 sm_state_map::print (const state_machine &sm, const region_model *model,
158 pretty_printer *pp) const
159 {
160 bool first = true;
161 pp_string (pp, "{");
162 if (m_global_state != 0)
163 {
164 pp_printf (pp, "global: %s", sm.get_state_name (m_global_state));
165 first = false;
166 }
167 for (map_t::iterator iter = m_map.begin ();
168 iter != m_map.end ();
169 ++iter)
170 {
171 if (!first)
172 pp_string (pp, ", ");
173 first = false;
174 svalue_id sid = (*iter).first;
175 sid.print (pp);
176
177 entry_t e = (*iter).second;
178 pp_printf (pp, ": %s", sm.get_state_name (e.m_state));
179 if (model)
180 if (tree rep = model->get_representative_tree (sid))
181 {
182 pp_string (pp, " (");
183 dump_quoted_tree (pp, rep);
184 pp_character (pp, ')');
185 }
186 if (!e.m_origin.null_p ())
187 {
188 pp_string (pp, " (origin: ");
189 e.m_origin.print (pp);
190 if (model)
191 if (tree rep = model->get_representative_tree (e.m_origin))
192 {
193 pp_string (pp, " (");
194 dump_quoted_tree (pp, rep);
195 pp_character (pp, ')');
196 }
197 pp_string (pp, ")");
198 }
199 }
200 pp_string (pp, "}");
201 }
202
203 /* Dump this object (for SM) to stderr. */
204
205 DEBUG_FUNCTION void
dump(const state_machine & sm) const206 sm_state_map::dump (const state_machine &sm) const
207 {
208 pretty_printer pp;
209 pp_show_color (&pp) = pp_show_color (global_dc->printer);
210 pp.buffer->stream = stderr;
211 print (sm, NULL, &pp);
212 pp_newline (&pp);
213 pp_flush (&pp);
214 }
215
216 /* Return true if no states have been set within this map
217 (all expressions are for the start state). */
218
219 bool
is_empty_p() const220 sm_state_map::is_empty_p () const
221 {
222 return m_map.elements () == 0 && m_global_state == 0;
223 }
224
225 /* Generate a hash value for this sm_state_map. */
226
227 hashval_t
hash() const228 sm_state_map::hash () const
229 {
230 hashval_t result = 0;
231
232 /* Accumulate the result by xoring a hash for each slot, so that the
233 result doesn't depend on the ordering of the slots in the map. */
234
235 for (map_t::iterator iter = m_map.begin ();
236 iter != m_map.end ();
237 ++iter)
238 {
239 inchash::hash hstate;
240 inchash::add ((*iter).first, hstate);
241 entry_t e = (*iter).second;
242 hstate.add_int (e.m_state);
243 inchash::add (e.m_origin, hstate);
244 result ^= hstate.end ();
245 }
246 result ^= m_global_state;
247
248 return result;
249 }
250
251 /* Equality operator for sm_state_map. */
252
253 bool
operator ==(const sm_state_map & other) const254 sm_state_map::operator== (const sm_state_map &other) const
255 {
256 if (m_global_state != other.m_global_state)
257 return false;
258
259 if (m_map.elements () != other.m_map.elements ())
260 return false;
261
262 for (map_t::iterator iter = m_map.begin ();
263 iter != m_map.end ();
264 ++iter)
265 {
266 svalue_id sid = (*iter).first;
267 entry_t e = (*iter).second;
268 entry_t *other_slot = const_cast <map_t &> (other.m_map).get (sid);
269 if (other_slot == NULL)
270 return false;
271 if (e != *other_slot)
272 return false;
273 }
274
275 gcc_checking_assert (hash () == other.hash ());
276
277 return true;
278 }
279
280 /* Get the state of SID within this object.
281 States default to the start state. */
282
283 state_machine::state_t
get_state(svalue_id sid) const284 sm_state_map::get_state (svalue_id sid) const
285 {
286 gcc_assert (!sid.null_p ());
287
288 if (entry_t *slot
289 = const_cast <map_t &> (m_map).get (sid))
290 return slot->m_state;
291 else
292 return 0;
293 }
294
295 /* Get the "origin" svalue_id for any state of SID. */
296
297 svalue_id
get_origin(svalue_id sid) const298 sm_state_map::get_origin (svalue_id sid) const
299 {
300 gcc_assert (!sid.null_p ());
301
302 entry_t *slot
303 = const_cast <map_t &> (m_map).get (sid);
304 if (slot)
305 return slot->m_origin;
306 else
307 return svalue_id::null ();
308 }
309
310 /* Set the state of SID within MODEL to STATE, recording that
311 the state came from ORIGIN. */
312
313 void
set_state(region_model * model,svalue_id sid,state_machine::state_t state,svalue_id origin)314 sm_state_map::set_state (region_model *model,
315 svalue_id sid,
316 state_machine::state_t state,
317 svalue_id origin)
318 {
319 if (model == NULL)
320 return;
321 equiv_class &ec = model->get_constraints ()->get_equiv_class (sid);
322 if (!set_state (ec, state, origin))
323 return;
324
325 /* Also do it for all svalues that are equal via non-cm, so that
326 e.g. (void *)&r and (foo *)&r transition together. */
327 for (unsigned i = 0; i < model->get_num_svalues (); i++)
328 {
329 svalue_id other_sid = svalue_id::from_int (i);
330 if (other_sid == sid)
331 continue;
332
333 tristate eq = model->eval_condition_without_cm (sid, EQ_EXPR, other_sid);
334 if (eq.is_true ())
335 impl_set_state (other_sid, state, origin);
336 }
337 }
338
339 /* Set the state of EC to STATE, recording that the state came from
340 ORIGIN.
341 Return true if any states of svalue_ids within EC changed. */
342
343 bool
set_state(const equiv_class & ec,state_machine::state_t state,svalue_id origin)344 sm_state_map::set_state (const equiv_class &ec,
345 state_machine::state_t state,
346 svalue_id origin)
347 {
348 int i;
349 svalue_id *sid;
350 bool any_changed = false;
351 FOR_EACH_VEC_ELT (ec.m_vars, i, sid)
352 any_changed |= impl_set_state (*sid, state, origin);
353 return any_changed;
354 }
355
356 /* Set state of SID to STATE, bypassing equivalence classes.
357 Return true if the state changed. */
358
359 bool
impl_set_state(svalue_id sid,state_machine::state_t state,svalue_id origin)360 sm_state_map::impl_set_state (svalue_id sid, state_machine::state_t state,
361 svalue_id origin)
362 {
363 if (get_state (sid) == state)
364 return false;
365
366 /* Special-case state 0 as the default value. */
367 if (state == 0)
368 {
369 if (m_map.get (sid))
370 m_map.remove (sid);
371 return true;
372 }
373 gcc_assert (!sid.null_p ());
374 m_map.put (sid, entry_t (state, origin));
375 return true;
376 }
377
378 /* Set the "global" state within this state map to STATE. */
379
380 void
set_global_state(state_machine::state_t state)381 sm_state_map::set_global_state (state_machine::state_t state)
382 {
383 m_global_state = state;
384 }
385
386 /* Get the "global" state within this state map. */
387
388 state_machine::state_t
get_global_state() const389 sm_state_map::get_global_state () const
390 {
391 return m_global_state;
392 }
393
394 /* Handle CALL to unknown FNDECL with an unknown function body, which
395 could do anything to the states passed to it.
396 Clear any state for SM for the params and any LHS.
397 Note that the function might be known to other state machines, but
398 not to this one. */
399
400 void
purge_for_unknown_fncall(const exploded_graph & eg,const state_machine & sm,const gcall * call,tree fndecl,region_model * new_model,region_model_context * ctxt)401 sm_state_map::purge_for_unknown_fncall (const exploded_graph &eg,
402 const state_machine &sm,
403 const gcall *call,
404 tree fndecl,
405 region_model *new_model,
406 region_model_context *ctxt)
407 {
408 logger * const logger = eg.get_logger ();
409 if (logger)
410 {
411 if (fndecl)
412 logger->log ("function %qE is unknown to checker %qs",
413 fndecl, sm.get_name ());
414 else
415 logger->log ("unknown function pointer for checker %qs",
416 sm.get_name ());
417 }
418
419 /* Purge any state for parms. */
420 tree iter_param_types = NULL_TREE;
421 if (fndecl)
422 iter_param_types = TYPE_ARG_TYPES (TREE_TYPE (fndecl));
423 for (unsigned arg_idx = 0; arg_idx < gimple_call_num_args (call); arg_idx++)
424 {
425 /* Track expected param type, where available. */
426 if (iter_param_types)
427 {
428 tree param_type = TREE_VALUE (iter_param_types);
429 gcc_assert (param_type);
430 iter_param_types = TREE_CHAIN (iter_param_types);
431
432 /* Don't purge state if it was passed as a const pointer
433 e.g. for things like strlen (PTR). */
434 if (TREE_CODE (param_type) == POINTER_TYPE)
435 if (TYPE_READONLY (TREE_TYPE (param_type)))
436 continue;
437 }
438 tree parm = gimple_call_arg (call, arg_idx);
439 svalue_id parm_sid = new_model->get_rvalue (parm, ctxt);
440 set_state (new_model, parm_sid, 0, svalue_id::null ());
441
442 /* Also clear sm-state from svalue_ids that are passed via a
443 pointer. */
444 if (TREE_CODE (parm) == ADDR_EXPR)
445 {
446 tree pointee = TREE_OPERAND (parm, 0);
447 svalue_id parm_sid = new_model->get_rvalue (pointee, ctxt);
448 set_state (new_model, parm_sid, 0, svalue_id::null ());
449 }
450 }
451
452 /* Purge any state for any LHS. */
453 if (tree lhs = gimple_call_lhs (call))
454 {
455 svalue_id lhs_sid = new_model->get_rvalue (lhs, ctxt);
456 set_state (new_model, lhs_sid, 0, svalue_id::null ());
457 }
458 }
459
460 /* Update this map based on MAP. */
461
462 void
remap_svalue_ids(const svalue_id_map & map)463 sm_state_map::remap_svalue_ids (const svalue_id_map &map)
464 {
465 map_t tmp_map;
466
467 /* Build an intermediate map, using the new sids. */
468 for (map_t::iterator iter = m_map.begin ();
469 iter != m_map.end ();
470 ++iter)
471 {
472 svalue_id sid = (*iter).first;
473 entry_t e = (*iter).second;
474
475 map.update (&sid);
476 map.update (&e.m_origin);
477 tmp_map.put (sid, e);
478 }
479
480 /* Clear the existing values. */
481 m_map.empty ();
482
483 /* Copy over from intermediate map. */
484 for (map_t::iterator iter = tmp_map.begin ();
485 iter != tmp_map.end ();
486 ++iter)
487 {
488 svalue_id sid = (*iter).first;
489 entry_t e = (*iter).second;
490
491 impl_set_state (sid, e.m_state, e.m_origin);
492 }
493 }
494
495 /* Purge any state for svalue_ids >= FIRST_UNUSED_SID.
496 If !SM::can_purge_p, then report the state as leaking,
497 using SM_IDX, CTXT, and MAP.
498 Return the number of states that were purged. */
499
500 int
on_svalue_purge(const state_machine & sm,int sm_idx,svalue_id first_unused_sid,const svalue_id_map & map,impl_region_model_context * ctxt)501 sm_state_map::on_svalue_purge (const state_machine &sm,
502 int sm_idx,
503 svalue_id first_unused_sid,
504 const svalue_id_map &map,
505 impl_region_model_context *ctxt)
506 {
507 /* TODO: ideally remove the slot directly; for now
508 do it in two stages. */
509 auto_vec<svalue_id> to_remove;
510 for (map_t::iterator iter = m_map.begin ();
511 iter != m_map.end ();
512 ++iter)
513 {
514 svalue_id dst_sid ((*iter).first);
515 if (dst_sid.as_int () >= first_unused_sid.as_int ())
516 {
517 /* Complain about leaks here. */
518 entry_t e = (*iter).second;
519
520 if (!sm.can_purge_p (e.m_state))
521 ctxt->on_state_leak (sm, sm_idx, dst_sid, first_unused_sid,
522 map, e.m_state);
523
524 to_remove.safe_push (dst_sid);
525 }
526 else if ((*iter).second.m_origin.as_int () >= first_unused_sid.as_int ())
527 {
528 /* If the origin svalue is being purged, then reset it to null. */
529 (*iter).second.m_origin = svalue_id::null ();
530 }
531 }
532
533 int i;
534 svalue_id *dst_sid;
535 FOR_EACH_VEC_ELT (to_remove, i, dst_sid)
536 m_map.remove (*dst_sid);
537
538 return to_remove.length ();
539 }
540
541 /* Set the state of CHILD_SID to that of PARENT_SID. */
542
543 void
on_inherited_svalue(svalue_id parent_sid,svalue_id child_sid)544 sm_state_map::on_inherited_svalue (svalue_id parent_sid,
545 svalue_id child_sid)
546 {
547 state_machine::state_t state = get_state (parent_sid);
548 impl_set_state (child_sid, state, parent_sid);
549 }
550
551 /* Set the state of DST_SID to that of SRC_SID. */
552
553 void
on_cast(svalue_id src_sid,svalue_id dst_sid)554 sm_state_map::on_cast (svalue_id src_sid,
555 svalue_id dst_sid)
556 {
557 state_machine::state_t state = get_state (src_sid);
558 impl_set_state (dst_sid, state, get_origin (src_sid));
559 }
560
561 /* Purge state from SID (in response to a call to an unknown function). */
562
563 void
on_unknown_change(svalue_id sid)564 sm_state_map::on_unknown_change (svalue_id sid)
565 {
566 impl_set_state (sid, (state_machine::state_t)0, svalue_id::null ());
567 }
568
569 /* Assert that this object is sane. */
570
571 void
validate(const state_machine & sm,int num_svalues) const572 sm_state_map::validate (const state_machine &sm,
573 int num_svalues) const
574 {
575 /* Skip this in a release build. */
576 #if !CHECKING_P
577 return;
578 #endif
579
580 for (map_t::iterator iter = m_map.begin ();
581 iter != m_map.end ();
582 ++iter)
583 {
584 svalue_id sid = (*iter).first;
585 entry_t e = (*iter).second;
586
587 gcc_assert (sid.as_int () < num_svalues);
588 sm.validate (e.m_state);
589 gcc_assert (e.m_origin.as_int () < num_svalues);
590 }
591 }
592
593 /* class program_state. */
594
595 /* program_state's ctor. */
596
program_state(const extrinsic_state & ext_state)597 program_state::program_state (const extrinsic_state &ext_state)
598 : m_region_model (new region_model ()),
599 m_checker_states (ext_state.get_num_checkers ()),
600 m_valid (true)
601 {
602 int num_states = ext_state.get_num_checkers ();
603 for (int i = 0; i < num_states; i++)
604 m_checker_states.quick_push (new sm_state_map ());
605 }
606
607 /* program_state's copy ctor. */
608
program_state(const program_state & other)609 program_state::program_state (const program_state &other)
610 : m_region_model (new region_model (*other.m_region_model)),
611 m_checker_states (other.m_checker_states.length ()),
612 m_valid (true)
613 {
614 int i;
615 sm_state_map *smap;
616 FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
617 m_checker_states.quick_push (smap->clone ());
618 }
619
620 /* program_state's assignment operator. */
621
622 program_state&
operator =(const program_state & other)623 program_state::operator= (const program_state &other)
624 {
625 delete m_region_model;
626 m_region_model = new region_model (*other.m_region_model);
627
628 int i;
629 sm_state_map *smap;
630 FOR_EACH_VEC_ELT (m_checker_states, i, smap)
631 delete smap;
632 m_checker_states.truncate (0);
633 gcc_assert (m_checker_states.space (other.m_checker_states.length ()));
634
635 FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
636 m_checker_states.quick_push (smap->clone ());
637
638 m_valid = other.m_valid;
639
640 return *this;
641 }
642
643 #if __cplusplus >= 201103
644 /* Move constructor for program_state (when building with C++11). */
program_state(program_state && other)645 program_state::program_state (program_state &&other)
646 : m_region_model (other.m_region_model),
647 m_checker_states (other.m_checker_states.length ())
648 {
649 other.m_region_model = NULL;
650
651 int i;
652 sm_state_map *smap;
653 FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
654 m_checker_states.quick_push (smap);
655 other.m_checker_states.truncate (0);
656
657 m_valid = other.m_valid;
658 }
659 #endif
660
661 /* program_state's dtor. */
662
~program_state()663 program_state::~program_state ()
664 {
665 delete m_region_model;
666 }
667
668 /* Generate a hash value for this program_state. */
669
670 hashval_t
hash() const671 program_state::hash () const
672 {
673 hashval_t result = m_region_model->hash ();
674
675 int i;
676 sm_state_map *smap;
677 FOR_EACH_VEC_ELT (m_checker_states, i, smap)
678 result ^= smap->hash ();
679 return result;
680 }
681
682 /* Equality operator for program_state.
683 All parts of the program_state (region model, checker states) must
684 equal their counterparts in OTHER for the two program_states to be
685 considered equal. */
686
687 bool
operator ==(const program_state & other) const688 program_state::operator== (const program_state &other) const
689 {
690 if (!(*m_region_model == *other.m_region_model))
691 return false;
692
693 int i;
694 sm_state_map *smap;
695 FOR_EACH_VEC_ELT (m_checker_states, i, smap)
696 if (!(*smap == *other.m_checker_states[i]))
697 return false;
698
699 gcc_checking_assert (hash () == other.hash ());
700
701 return true;
702 }
703
704 /* Print a compact representation of this state to PP. */
705
706 void
print(const extrinsic_state & ext_state,pretty_printer * pp) const707 program_state::print (const extrinsic_state &ext_state,
708 pretty_printer *pp) const
709 {
710 pp_printf (pp, "rmodel: ");
711 m_region_model->print (pp);
712 pp_newline (pp);
713
714 int i;
715 sm_state_map *smap;
716 FOR_EACH_VEC_ELT (m_checker_states, i, smap)
717 {
718 if (!smap->is_empty_p ())
719 {
720 pp_printf (pp, "%s: ", ext_state.get_name (i));
721 smap->print (ext_state.get_sm (i), m_region_model, pp);
722 pp_newline (pp);
723 }
724 }
725 if (!m_valid)
726 {
727 pp_printf (pp, "invalid state");
728 pp_newline (pp);
729 }
730 }
731
732 /* Dump a representation of this state to PP.
733 If SUMMARIZE is true, print a one-line summary;
734 if false, print a detailed multiline representation. */
735
736 void
dump_to_pp(const extrinsic_state & ext_state,bool summarize,pretty_printer * pp) const737 program_state::dump_to_pp (const extrinsic_state &ext_state,
738 bool summarize,
739 pretty_printer *pp) const
740 {
741 pp_printf (pp, "rmodel: ");
742 m_region_model->dump_to_pp (pp, summarize);
743
744 int i;
745 sm_state_map *smap;
746 FOR_EACH_VEC_ELT (m_checker_states, i, smap)
747 {
748 if (!smap->is_empty_p ())
749 {
750 if (summarize)
751 pp_space (pp);
752 pp_printf (pp, "%s: ", ext_state.get_name (i));
753 smap->print (ext_state.get_sm (i), m_region_model, pp);
754 if (!summarize)
755 pp_newline (pp);
756 }
757 }
758
759 if (!m_valid)
760 {
761 if (summarize)
762 pp_space (pp);
763 pp_printf (pp, "invalid state");
764 if (!summarize)
765 pp_newline (pp);
766 }
767 }
768
769 /* Dump a multiline representation of this state to OUTF. */
770
771 void
dump_to_file(const extrinsic_state & ext_state,bool summarize,FILE * outf) const772 program_state::dump_to_file (const extrinsic_state &ext_state,
773 bool summarize,
774 FILE *outf) const
775 {
776 pretty_printer pp;
777 pp_format_decoder (&pp) = default_tree_printer;
778 if (outf == stderr)
779 pp_show_color (&pp) = pp_show_color (global_dc->printer);
780 pp.buffer->stream = outf;
781 dump_to_pp (ext_state, summarize, &pp);
782 pp_flush (&pp);
783 }
784
785 /* Dump a multiline representation of this state to stderr. */
786
787 DEBUG_FUNCTION void
dump(const extrinsic_state & ext_state,bool summarize) const788 program_state::dump (const extrinsic_state &ext_state,
789 bool summarize) const
790 {
791 dump_to_file (ext_state, summarize, stderr);
792 }
793
794 /* Determine if following edge SUCC from ENODE is valid within the graph EG
795 and update this state accordingly in-place.
796
797 Return true if the edge can be followed, or false otherwise.
798
799 Check for relevant conditionals and switch-values for conditionals
800 and switch statements, adding the relevant conditions to this state.
801 Push/pop frames for interprocedural edges and update params/returned
802 values.
803
804 This is the "state" half of exploded_node::on_edge. */
805
806 bool
on_edge(exploded_graph & eg,const exploded_node & enode,const superedge * succ,state_change * change)807 program_state::on_edge (exploded_graph &eg,
808 const exploded_node &enode,
809 const superedge *succ,
810 state_change *change)
811 {
812 /* Update state. */
813 const program_point &point = enode.get_point ();
814 const gimple *last_stmt = point.get_supernode ()->get_last_stmt ();
815
816 /* For conditionals and switch statements, add the
817 relevant conditions (for the specific edge) to new_state;
818 skip edges for which the resulting constraints
819 are impossible.
820 This also updates frame information for call/return superedges.
821 Adding the relevant conditions for the edge could also trigger
822 sm-state transitions (e.g. transitions due to ptrs becoming known
823 to be NULL or non-NULL) */
824
825 impl_region_model_context ctxt (eg, &enode,
826 &enode.get_state (),
827 this, change,
828 last_stmt);
829 if (!m_region_model->maybe_update_for_edge (*succ,
830 last_stmt,
831 &ctxt))
832 {
833 logger * const logger = eg.get_logger ();
834 if (logger)
835 logger->log ("edge to SN: %i is impossible"
836 " due to region_model constraints",
837 succ->m_dest->m_index);
838 return false;
839 }
840
841 return true;
842 }
843
844 /* Generate a simpler version of THIS, discarding state that's no longer
845 relevant at POINT.
846 The idea is that we're more likely to be able to consolidate
847 multiple (point, state) into single exploded_nodes if we discard
848 irrelevant state (e.g. at the end of functions).
849
850 Retain state affected by CHANGE, to make it easier to generate
851 state_change_events. */
852
853 program_state
prune_for_point(exploded_graph & eg,const program_point & point,state_change * change) const854 program_state::prune_for_point (exploded_graph &eg,
855 const program_point &point,
856 state_change *change) const
857 {
858 logger * const logger = eg.get_logger ();
859 LOG_SCOPE (logger);
860
861 function *fun = point.get_function ();
862 if (!fun)
863 return *this;
864
865 program_state new_state (*this);
866
867 purge_stats stats;
868
869 const state_purge_map *pm = eg.get_purge_map ();
870 if (pm)
871 {
872 region_id_set purgeable_ssa_regions (new_state.m_region_model);
873 region_id frame_rid
874 = new_state.m_region_model->get_current_frame_id ();
875 frame_region *frame
876 = new_state.m_region_model->get_region <frame_region>(frame_rid);
877
878 /* TODO: maybe move to a member of region_model? */
879
880 auto_vec<tree> ssa_names_to_purge;
881 for (frame_region::map_t::iterator iter = frame->begin ();
882 iter != frame->end ();
883 ++iter)
884 {
885 tree var = (*iter).first;
886 region_id rid = (*iter).second;
887 if (TREE_CODE (var) == SSA_NAME)
888 {
889 const state_purge_per_ssa_name &per_ssa
890 = pm->get_data_for_ssa_name (var);
891 if (!per_ssa.needed_at_point_p (point.get_function_point ()))
892 {
893 region *region
894 = new_state.m_region_model->get_region (rid);
895 svalue_id sid = region->get_value_direct ();
896 if (!sid.null_p ())
897 {
898 if (!new_state.can_purge_p (eg.get_ext_state (), sid))
899 {
900 /* (currently only state maps can keep things
901 alive). */
902 if (logger)
903 logger->log ("not purging RID: %i for %qE"
904 " (used by state map)",
905 rid.as_int (), var);
906 continue;
907 }
908
909 /* Don't purge regions containing svalues that
910 have a change of sm-state, to make it easier to
911 generate state_change_event messages. */
912 if (change)
913 if (change->affects_p (sid))
914 {
915 if (logger)
916 logger->log ("not purging RID: %i for %qE"
917 " (affected by change)",
918 rid.as_int (), var);
919 continue;
920 }
921 }
922 purgeable_ssa_regions.add_region (rid);
923 ssa_names_to_purge.safe_push (var);
924 if (logger)
925 logger->log ("purging RID: %i for %qE", rid.as_int (), var);
926 /* We also need to remove the region from the map.
927 We're in mid-traversal, so the removal is done in
928 unbind below. */
929 }
930 }
931 }
932
933 /* Unbind the regions from the frame's map of vars-to-regions. */
934 unsigned i;
935 tree var;
936 FOR_EACH_VEC_ELT (ssa_names_to_purge, i, var)
937 frame->unbind (var);
938
939 /* Purge the regions. Nothing should point to them, and they
940 should have no children, as they are for SSA names. */
941 new_state.m_region_model->purge_regions (purgeable_ssa_regions,
942 &stats,
943 eg.get_logger ());
944 }
945
946 /* Purge unused svalues. */
947 // TODO: which enode to use, if any?
948 impl_region_model_context ctxt (eg, NULL,
949 this,
950 &new_state,
951 change,
952 NULL);
953 new_state.m_region_model->purge_unused_svalues (&stats, &ctxt);
954 if (logger)
955 {
956 logger->log ("num svalues purged: %i", stats.m_num_svalues);
957 logger->log ("num regions purged: %i", stats.m_num_regions);
958 logger->log ("num equiv_classes purged: %i", stats.m_num_equiv_classes);
959 logger->log ("num constraints purged: %i", stats.m_num_constraints);
960 logger->log ("num sm map items purged: %i", stats.m_num_client_items);
961 }
962
963 new_state.m_region_model->canonicalize (&ctxt);
964
965 return new_state;
966 }
967
968 /* Remap all svalue_ids in this state's m_checker_states according to MAP.
969 The svalues_ids in the region_model are assumed to already have been
970 remapped. */
971
972 void
remap_svalue_ids(const svalue_id_map & map)973 program_state::remap_svalue_ids (const svalue_id_map &map)
974 {
975 int i;
976 sm_state_map *smap;
977 FOR_EACH_VEC_ELT (m_checker_states, i, smap)
978 smap->remap_svalue_ids (map);
979 }
980
981 /* Attempt to return a tree that represents SID, or return NULL_TREE.
982 Find the first region that stores the value (e.g. a local) and
983 generate a representative tree for it. */
984
985 tree
get_representative_tree(svalue_id sid) const986 program_state::get_representative_tree (svalue_id sid) const
987 {
988 return m_region_model->get_representative_tree (sid);
989 }
990
991 /* Attempt to merge this state with OTHER, both using EXT_STATE.
992 Write the result to *OUT.
993 If the states were merged successfully, return true. */
994
995 bool
can_merge_with_p(const program_state & other,const extrinsic_state & ext_state,program_state * out) const996 program_state::can_merge_with_p (const program_state &other,
997 const extrinsic_state &ext_state,
998 program_state *out) const
999 {
1000 gcc_assert (out);
1001
1002 /* TODO: initially I had an early reject here if there
1003 are sm-differences between the states. However, this was
1004 falsely rejecting merger opportunities for states where the
1005 only difference was in svalue_id ordering. */
1006
1007 /* Attempt to merge the region_models. */
1008
1009 svalue_id_merger_mapping sid_mapping (*m_region_model,
1010 *other.m_region_model);
1011 if (!m_region_model->can_merge_with_p (*other.m_region_model,
1012 out->m_region_model,
1013 &sid_mapping))
1014 return false;
1015
1016 /* Copy m_checker_states to result, remapping svalue_ids using
1017 sid_mapping. */
1018 int i;
1019 sm_state_map *smap;
1020 FOR_EACH_VEC_ELT (out->m_checker_states, i, smap)
1021 delete smap;
1022 out->m_checker_states.truncate (0);
1023
1024 /* Remap this and other's m_checker_states using sid_mapping.
1025 Only merge states that have equality between the two end-results:
1026 sm-state differences are likely to be interesting to end-users, and
1027 hence are worth exploring as separate paths in the exploded graph. */
1028 FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1029 {
1030 sm_state_map *other_smap = other.m_checker_states[i];
1031
1032 /* If clone_with_remapping returns NULL for one of the input smaps,
1033 then it has sm-state for an svalue_id where the svalue_id is
1034 being mapped to svalue_id::null in its sid_mapping, meaning that
1035 the svalue is to be dropped during the merger. We don't want
1036 to lose sm-state during a state merger, so return false for these
1037 cases. */
1038 sm_state_map *remapped_a_smap
1039 = smap->clone_with_remapping (sid_mapping.m_map_from_a_to_m);
1040 if (!remapped_a_smap)
1041 return false;
1042 sm_state_map *remapped_b_smap
1043 = other_smap->clone_with_remapping (sid_mapping.m_map_from_b_to_m);
1044 if (!remapped_b_smap)
1045 {
1046 delete remapped_a_smap;
1047 return false;
1048 }
1049
1050 /* Both states have sm-state for the same values; now ensure that the
1051 states are equal. */
1052 if (*remapped_a_smap == *remapped_b_smap)
1053 {
1054 out->m_checker_states.safe_push (remapped_a_smap);
1055 delete remapped_b_smap;
1056 }
1057 else
1058 {
1059 /* Don't merge if there are sm-state differences. */
1060 delete remapped_a_smap;
1061 delete remapped_b_smap;
1062 return false;
1063 }
1064 }
1065
1066 impl_region_model_context ctxt (out, NULL, ext_state);
1067 out->m_region_model->canonicalize (&ctxt);
1068
1069 return true;
1070 }
1071
1072 /* Assert that this object is valid. */
1073
1074 void
validate(const extrinsic_state & ext_state) const1075 program_state::validate (const extrinsic_state &ext_state) const
1076 {
1077 /* Skip this in a release build. */
1078 #if !CHECKING_P
1079 return;
1080 #endif
1081
1082 m_region_model->validate ();
1083 gcc_assert (m_checker_states.length () == ext_state.get_num_checkers ());
1084 int sm_idx;
1085 sm_state_map *smap;
1086 FOR_EACH_VEC_ELT (m_checker_states, sm_idx, smap)
1087 {
1088 const state_machine &sm = ext_state.get_sm (sm_idx);
1089 smap->validate (sm, m_region_model->get_num_svalues ());
1090 }
1091 }
1092
1093 /* Dump this sm_change to PP. */
1094
1095 void
dump(pretty_printer * pp,const extrinsic_state & ext_state) const1096 state_change::sm_change::dump (pretty_printer *pp,
1097 const extrinsic_state &ext_state) const
1098 {
1099 const state_machine &sm = get_sm (ext_state);
1100 pp_string (pp, "(");
1101 m_new_sid.print (pp);
1102 pp_printf (pp, ": %s: %qs -> %qs)",
1103 sm.get_name (),
1104 sm.get_state_name (m_old_state),
1105 sm.get_state_name (m_new_state));
1106 }
1107
1108 /* Remap all svalue_ids in this change according to MAP. */
1109
1110 void
remap_svalue_ids(const svalue_id_map & map)1111 state_change::sm_change::remap_svalue_ids (const svalue_id_map &map)
1112 {
1113 map.update (&m_new_sid);
1114 }
1115
1116 /* Purge any svalue_ids >= FIRST_UNUSED_SID.
1117 Return the number of states that were purged. */
1118
1119 int
on_svalue_purge(svalue_id first_unused_sid)1120 state_change::sm_change::on_svalue_purge (svalue_id first_unused_sid)
1121 {
1122 if (m_new_sid.as_int () >= first_unused_sid.as_int ())
1123 {
1124 m_new_sid = svalue_id::null ();
1125 return 1;
1126 }
1127
1128 return 0;
1129 }
1130
1131 /* Assert that this object is sane. */
1132
1133 void
validate(const program_state & new_state,const extrinsic_state & ext_state) const1134 state_change::sm_change::validate (const program_state &new_state,
1135 const extrinsic_state &ext_state) const
1136 {
1137 gcc_assert ((unsigned)m_sm_idx < ext_state.get_num_checkers ());
1138 const state_machine &sm = ext_state.get_sm (m_sm_idx);
1139 sm.validate (m_old_state);
1140 sm.validate (m_new_state);
1141 m_new_sid.validate (*new_state.m_region_model);
1142 }
1143
1144 /* state_change's ctor. */
1145
state_change()1146 state_change::state_change ()
1147 {
1148 }
1149
1150 /* state_change's copy ctor. */
1151
state_change(const state_change & other)1152 state_change::state_change (const state_change &other)
1153 : m_sm_changes (other.m_sm_changes.length ())
1154 {
1155 unsigned i;
1156 sm_change *change;
1157 FOR_EACH_VEC_ELT (other.m_sm_changes, i, change)
1158 m_sm_changes.quick_push (*change);
1159 }
1160
1161 /* Record a state-machine state change. */
1162
1163 void
add_sm_change(int sm_idx,svalue_id new_sid,state_machine::state_t old_state,state_machine::state_t new_state)1164 state_change::add_sm_change (int sm_idx,
1165 svalue_id new_sid,
1166 state_machine::state_t old_state,
1167 state_machine::state_t new_state)
1168 {
1169 m_sm_changes.safe_push (sm_change (sm_idx,
1170 new_sid,
1171 old_state, new_state));
1172 }
1173
1174 /* Return true if SID (in the new state) was affected by any
1175 sm-state changes. */
1176
1177 bool
affects_p(svalue_id sid) const1178 state_change::affects_p (svalue_id sid) const
1179 {
1180 unsigned i;
1181 sm_change *change;
1182 FOR_EACH_VEC_ELT (m_sm_changes, i, change)
1183 {
1184 if (sid == change->m_new_sid)
1185 return true;
1186 }
1187 return false;
1188 }
1189
1190 /* Dump this state_change to PP. */
1191
1192 void
dump(pretty_printer * pp,const extrinsic_state & ext_state) const1193 state_change::dump (pretty_printer *pp,
1194 const extrinsic_state &ext_state) const
1195 {
1196 unsigned i;
1197 sm_change *change;
1198 FOR_EACH_VEC_ELT (m_sm_changes, i, change)
1199 {
1200 if (i > 0)
1201 pp_string (pp, ", ");
1202 change->dump (pp, ext_state);
1203 }
1204 }
1205
1206 /* Dump this state_change to stderr. */
1207
1208 void
dump(const extrinsic_state & ext_state) const1209 state_change::dump (const extrinsic_state &ext_state) const
1210 {
1211 pretty_printer pp;
1212 pp_show_color (&pp) = pp_show_color (global_dc->printer);
1213 pp.buffer->stream = stderr;
1214 dump (&pp, ext_state);
1215 pp_newline (&pp);
1216 pp_flush (&pp);
1217 }
1218
1219 /* Remap all svalue_ids in this state_change according to MAP. */
1220
1221 void
remap_svalue_ids(const svalue_id_map & map)1222 state_change::remap_svalue_ids (const svalue_id_map &map)
1223 {
1224 unsigned i;
1225 sm_change *change;
1226 FOR_EACH_VEC_ELT (m_sm_changes, i, change)
1227 change->remap_svalue_ids (map);
1228 }
1229
1230 /* Purge any svalue_ids >= FIRST_UNUSED_SID.
1231 Return the number of states that were purged. */
1232
1233 int
on_svalue_purge(svalue_id first_unused_sid)1234 state_change::on_svalue_purge (svalue_id first_unused_sid)
1235 {
1236 int result = 0;
1237 unsigned i;
1238 sm_change *change;
1239 FOR_EACH_VEC_ELT (m_sm_changes, i, change)
1240 result += change->on_svalue_purge (first_unused_sid);
1241 return result;
1242 }
1243
1244 /* Assert that this object is sane. */
1245
1246 void
validate(const program_state & new_state,const extrinsic_state & ext_state) const1247 state_change::validate (const program_state &new_state,
1248 const extrinsic_state &ext_state) const
1249 {
1250 /* Skip this in a release build. */
1251 #if !CHECKING_P
1252 return;
1253 #endif
1254 unsigned i;
1255 sm_change *change;
1256 FOR_EACH_VEC_ELT (m_sm_changes, i, change)
1257 change->validate (new_state, ext_state);
1258 }
1259
1260 #if CHECKING_P
1261
1262 namespace selftest {
1263
1264 /* Implementation detail of ASSERT_DUMP_EQ. */
1265
1266 static void
assert_dump_eq(const location & loc,const program_state & state,const extrinsic_state & ext_state,bool summarize,const char * expected)1267 assert_dump_eq (const location &loc,
1268 const program_state &state,
1269 const extrinsic_state &ext_state,
1270 bool summarize,
1271 const char *expected)
1272 {
1273 auto_fix_quotes sentinel;
1274 pretty_printer pp;
1275 pp_format_decoder (&pp) = default_tree_printer;
1276 state.dump_to_pp (ext_state, summarize, &pp);
1277 ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
1278 }
1279
1280 /* Assert that STATE.dump_to_pp (SUMMARIZE) is EXPECTED. */
1281
1282 #define ASSERT_DUMP_EQ(STATE, EXT_STATE, SUMMARIZE, EXPECTED) \
1283 SELFTEST_BEGIN_STMT \
1284 assert_dump_eq ((SELFTEST_LOCATION), (STATE), (EXT_STATE), (SUMMARIZE), \
1285 (EXPECTED)); \
1286 SELFTEST_END_STMT
1287
1288 /* Tests for sm_state_map. */
1289
1290 static void
test_sm_state_map()1291 test_sm_state_map ()
1292 {
1293 tree x = build_global_decl ("x", integer_type_node);
1294 tree y = build_global_decl ("y", integer_type_node);
1295 tree z = build_global_decl ("z", integer_type_node);
1296
1297 /* Test setting states on svalue_id instances directly. */
1298 {
1299 region_model model;
1300 svalue_id sid_x = model.get_rvalue (x, NULL);
1301 svalue_id sid_y = model.get_rvalue (y, NULL);
1302 svalue_id sid_z = model.get_rvalue (z, NULL);
1303
1304 sm_state_map map;
1305 ASSERT_TRUE (map.is_empty_p ());
1306 ASSERT_EQ (map.get_state (sid_x), 0);
1307
1308 map.impl_set_state (sid_x, 42, sid_z);
1309 ASSERT_EQ (map.get_state (sid_x), 42);
1310 ASSERT_EQ (map.get_origin (sid_x), sid_z);
1311 ASSERT_EQ (map.get_state (sid_y), 0);
1312 ASSERT_FALSE (map.is_empty_p ());
1313
1314 map.impl_set_state (sid_y, 0, sid_z);
1315 ASSERT_EQ (map.get_state (sid_y), 0);
1316
1317 map.impl_set_state (sid_x, 0, sid_z);
1318 ASSERT_EQ (map.get_state (sid_x), 0);
1319 ASSERT_TRUE (map.is_empty_p ());
1320 }
1321
1322 /* Test setting states via equivalence classes. */
1323 {
1324 region_model model;
1325 svalue_id sid_x = model.get_rvalue (x, NULL);
1326 svalue_id sid_y = model.get_rvalue (y, NULL);
1327 svalue_id sid_z = model.get_rvalue (z, NULL);
1328
1329 sm_state_map map;
1330 ASSERT_TRUE (map.is_empty_p ());
1331 ASSERT_EQ (map.get_state (sid_x), 0);
1332 ASSERT_EQ (map.get_state (sid_y), 0);
1333
1334 model.add_constraint (x, EQ_EXPR, y, NULL);
1335
1336 /* Setting x to a state should also update y, as they
1337 are in the same equivalence class. */
1338 map.set_state (&model, sid_x, 5, sid_z);
1339 ASSERT_EQ (map.get_state (sid_x), 5);
1340 ASSERT_EQ (map.get_state (sid_y), 5);
1341 ASSERT_EQ (map.get_origin (sid_x), sid_z);
1342 ASSERT_EQ (map.get_origin (sid_y), sid_z);
1343 }
1344
1345 /* Test equality and hashing. */
1346 {
1347 region_model model;
1348 svalue_id sid_y = model.get_rvalue (y, NULL);
1349 svalue_id sid_z = model.get_rvalue (z, NULL);
1350
1351 sm_state_map map0;
1352 sm_state_map map1;
1353 sm_state_map map2;
1354
1355 ASSERT_EQ (map0.hash (), map1.hash ());
1356 ASSERT_EQ (map0, map1);
1357
1358 map1.impl_set_state (sid_y, 5, sid_z);
1359 ASSERT_NE (map0.hash (), map1.hash ());
1360 ASSERT_NE (map0, map1);
1361
1362 /* Make the same change to map2. */
1363 map2.impl_set_state (sid_y, 5, sid_z);
1364 ASSERT_EQ (map1.hash (), map2.hash ());
1365 ASSERT_EQ (map1, map2);
1366 }
1367
1368 /* Equality and hashing shouldn't depend on ordering. */
1369 {
1370 sm_state_map map0;
1371 sm_state_map map1;
1372 sm_state_map map2;
1373
1374 ASSERT_EQ (map0.hash (), map1.hash ());
1375 ASSERT_EQ (map0, map1);
1376
1377 map1.impl_set_state (svalue_id::from_int (14), 2, svalue_id::null ());
1378 map1.impl_set_state (svalue_id::from_int (16), 3, svalue_id::null ());
1379 map1.impl_set_state (svalue_id::from_int (1), 2, svalue_id::null ());
1380 map1.impl_set_state (svalue_id::from_int (9), 2, svalue_id::null ());
1381
1382 map2.impl_set_state (svalue_id::from_int (1), 2, svalue_id::null ());
1383 map2.impl_set_state (svalue_id::from_int (16), 3, svalue_id::null ());
1384 map2.impl_set_state (svalue_id::from_int (14), 2, svalue_id::null ());
1385 map2.impl_set_state (svalue_id::from_int (9), 2, svalue_id::null ());
1386
1387 ASSERT_EQ (map1.hash (), map2.hash ());
1388 ASSERT_EQ (map1, map2);
1389 }
1390
1391 /* Test sm_state_map::remap_svalue_ids. */
1392 {
1393 sm_state_map map;
1394 svalue_id sid_0 = svalue_id::from_int (0);
1395 svalue_id sid_1 = svalue_id::from_int (1);
1396 svalue_id sid_2 = svalue_id::from_int (2);
1397
1398 map.impl_set_state (sid_0, 42, sid_2);
1399 ASSERT_EQ (map.get_state (sid_0), 42);
1400 ASSERT_EQ (map.get_origin (sid_0), sid_2);
1401 ASSERT_EQ (map.get_state (sid_1), 0);
1402 ASSERT_EQ (map.get_state (sid_2), 0);
1403
1404 /* Apply a remapping to the IDs. */
1405 svalue_id_map remapping (3);
1406 remapping.put (sid_0, sid_1);
1407 remapping.put (sid_1, sid_2);
1408 remapping.put (sid_2, sid_0);
1409 map.remap_svalue_ids (remapping);
1410
1411 /* Verify that the IDs have been remapped. */
1412 ASSERT_EQ (map.get_state (sid_1), 42);
1413 ASSERT_EQ (map.get_origin (sid_1), sid_0);
1414 ASSERT_EQ (map.get_state (sid_2), 0);
1415 ASSERT_EQ (map.get_state (sid_0), 0);
1416 }
1417
1418 // TODO: coverage for purging
1419 }
1420
1421 /* Verify that program_state::dump_to_pp works as expected. */
1422
1423 static void
test_program_state_dumping()1424 test_program_state_dumping ()
1425 {
1426 /* Create a program_state for a global ptr "p" that has
1427 malloc sm-state, pointing to a region on the heap. */
1428 tree p = build_global_decl ("p", ptr_type_node);
1429
1430 state_machine *sm = make_malloc_state_machine (NULL);
1431 const state_machine::state_t UNCHECKED_STATE
1432 = sm->get_state_by_name ("unchecked");
1433 auto_delete_vec <state_machine> checkers;
1434 checkers.safe_push (sm);
1435 extrinsic_state ext_state (checkers);
1436
1437 program_state s (ext_state);
1438 region_model *model = s.m_region_model;
1439 region_id new_rid = model->add_new_malloc_region ();
1440 svalue_id ptr_sid
1441 = model->get_or_create_ptr_svalue (ptr_type_node, new_rid);
1442 model->set_value (model->get_lvalue (p, NULL),
1443 ptr_sid, NULL);
1444 sm_state_map *smap = s.m_checker_states[0];
1445
1446 smap->impl_set_state (ptr_sid, UNCHECKED_STATE, svalue_id::null ());
1447 ASSERT_EQ (smap->get_state (ptr_sid), UNCHECKED_STATE);
1448
1449 ASSERT_DUMP_EQ
1450 (s, ext_state, false,
1451 "rmodel: r0: {kind: `root', parent: null, sval: null}\n"
1452 "|-heap: r1: {kind: `heap', parent: r0, sval: null}\n"
1453 "| `-r2: {kind: `symbolic', parent: r1, sval: null, possibly_null: true}\n"
1454 "`-globals: r3: {kind: `globals', parent: r0, sval: null, map: {`p': r4}}\n"
1455 " `-`p': r4: {kind: `primitive', parent: r3, sval: sv0, type: `void *'}\n"
1456 " |: sval: sv0: {type: `void *', &r2}\n"
1457 " |: type: `void *'\n"
1458 "svalues:\n"
1459 " sv0: {type: `void *', &r2}\n"
1460 "constraint manager:\n"
1461 " equiv classes:\n"
1462 " constraints:\n"
1463 "malloc: {sv0: unchecked (`p')}\n");
1464
1465 ASSERT_DUMP_EQ (s, ext_state, true,
1466 "rmodel: p: &r2 malloc: {sv0: unchecked (`p')}");
1467 }
1468
1469 /* Verify that program_state::dump_to_pp works for string literals. */
1470
1471 static void
test_program_state_dumping_2()1472 test_program_state_dumping_2 ()
1473 {
1474 /* Create a program_state for a global ptr "p" that points to
1475 a string constant. */
1476 tree p = build_global_decl ("p", ptr_type_node);
1477
1478 tree string_cst_ptr = build_string_literal (4, "foo");
1479
1480 auto_delete_vec <state_machine> checkers;
1481 extrinsic_state ext_state (checkers);
1482
1483 program_state s (ext_state);
1484 region_model *model = s.m_region_model;
1485 region_id p_rid = model->get_lvalue (p, NULL);
1486 svalue_id str_sid = model->get_rvalue (string_cst_ptr, NULL);
1487 model->set_value (p_rid, str_sid, NULL);
1488
1489 ASSERT_DUMP_EQ
1490 (s, ext_state, false,
1491 "rmodel: r0: {kind: `root', parent: null, sval: null}\n"
1492 "|-globals: r1: {kind: `globals', parent: r0, sval: null, map: {`p': r2}}\n"
1493 "| `-`p': r2: {kind: `primitive', parent: r1, sval: sv3, type: `void *'}\n"
1494 "| |: sval: sv3: {type: `void *', &r4}\n"
1495 "| |: type: `void *'\n"
1496 "`-r3: {kind: `array', parent: r0, sval: sv0, type: `const char[4]', array: {[0]: r4}}\n"
1497 " |: sval: sv0: {type: `const char[4]', `\"foo\"'}\n"
1498 " |: type: `const char[4]'\n"
1499 " `-[0]: r4: {kind: `primitive', parent: r3, sval: null, type: `const char'}\n"
1500 " |: type: `const char'\n"
1501 "svalues:\n"
1502 " sv0: {type: `const char[4]', `\"foo\"'}\n"
1503 " sv1: {type: `int', `0'}\n"
1504 " sv2: {type: `const char *', &r4}\n"
1505 " sv3: {type: `void *', &r4}\n"
1506 "constraint manager:\n"
1507 " equiv classes:\n"
1508 " constraints:\n");
1509
1510 ASSERT_DUMP_EQ (s, ext_state, true,
1511 "rmodel: p: &\"foo\"[0]");
1512 }
1513
1514 /* Verify that program_states with identical sm-state can be merged,
1515 and that the merged program_state preserves the sm-state. */
1516
1517 static void
test_program_state_merging()1518 test_program_state_merging ()
1519 {
1520 /* Create a program_state for a global ptr "p" that has
1521 malloc sm-state, pointing to a region on the heap. */
1522 tree p = build_global_decl ("p", ptr_type_node);
1523
1524 auto_delete_vec <state_machine> checkers;
1525 checkers.safe_push (make_malloc_state_machine (NULL));
1526 extrinsic_state ext_state (checkers);
1527
1528 program_state s0 (ext_state);
1529 impl_region_model_context ctxt (&s0, NULL, ext_state);
1530
1531 region_model *model0 = s0.m_region_model;
1532 region_id new_rid = model0->add_new_malloc_region ();
1533 svalue_id ptr_sid
1534 = model0->get_or_create_ptr_svalue (ptr_type_node, new_rid);
1535 model0->set_value (model0->get_lvalue (p, &ctxt),
1536 ptr_sid, &ctxt);
1537 sm_state_map *smap = s0.m_checker_states[0];
1538 const state_machine::state_t TEST_STATE = 3;
1539 smap->impl_set_state (ptr_sid, TEST_STATE, svalue_id::null ());
1540 ASSERT_EQ (smap->get_state (ptr_sid), TEST_STATE);
1541
1542 model0->canonicalize (&ctxt);
1543
1544 /* Verify that canonicalization preserves sm-state. */
1545 ASSERT_EQ (smap->get_state (model0->get_rvalue (p, NULL)), TEST_STATE);
1546
1547 /* Make a copy of the program_state. */
1548 program_state s1 (s0);
1549 ASSERT_EQ (s0, s1);
1550
1551 /* We have two identical states with "p" pointing to a heap region
1552 with the given sm-state.
1553 They ought to be mergeable, preserving the sm-state. */
1554 program_state merged (ext_state);
1555 ASSERT_TRUE (s0.can_merge_with_p (s1, ext_state, &merged));
1556 merged.validate (ext_state);
1557
1558 /* Verify that the merged state has the sm-state for "p". */
1559 region_model *merged_model = merged.m_region_model;
1560 sm_state_map *merged_smap = merged.m_checker_states[0];
1561 ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, NULL)),
1562 TEST_STATE);
1563
1564 /* Try canonicalizing. */
1565 impl_region_model_context merged_ctxt (&merged, NULL, ext_state);
1566 merged.m_region_model->canonicalize (&merged_ctxt);
1567 merged.validate (ext_state);
1568
1569 /* Verify that the merged state still has the sm-state for "p". */
1570 ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, NULL)),
1571 TEST_STATE);
1572
1573 /* After canonicalization, we ought to have equality with the inputs. */
1574 ASSERT_EQ (s0, merged);
1575 }
1576
1577 /* Verify that program_states with different global-state in an sm-state
1578 can't be merged. */
1579
1580 static void
test_program_state_merging_2()1581 test_program_state_merging_2 ()
1582 {
1583 auto_delete_vec <state_machine> checkers;
1584 checkers.safe_push (make_signal_state_machine (NULL));
1585 extrinsic_state ext_state (checkers);
1586
1587 program_state s0 (ext_state);
1588 {
1589 sm_state_map *smap0 = s0.m_checker_states[0];
1590 const state_machine::state_t TEST_STATE_0 = 0;
1591 smap0->set_global_state (TEST_STATE_0);
1592 ASSERT_EQ (smap0->get_global_state (), TEST_STATE_0);
1593 }
1594
1595 program_state s1 (ext_state);
1596 {
1597 sm_state_map *smap1 = s1.m_checker_states[0];
1598 const state_machine::state_t TEST_STATE_1 = 1;
1599 smap1->set_global_state (TEST_STATE_1);
1600 ASSERT_EQ (smap1->get_global_state (), TEST_STATE_1);
1601 }
1602
1603 ASSERT_NE (s0, s1);
1604
1605 /* They ought to not be mergeable. */
1606 program_state merged (ext_state);
1607 ASSERT_FALSE (s0.can_merge_with_p (s1, ext_state, &merged));
1608 }
1609
1610 /* Run all of the selftests within this file. */
1611
1612 void
analyzer_program_state_cc_tests()1613 analyzer_program_state_cc_tests ()
1614 {
1615 test_sm_state_map ();
1616 test_program_state_dumping ();
1617 test_program_state_dumping_2 ();
1618 test_program_state_merging ();
1619 test_program_state_merging_2 ();
1620 }
1621
1622 } // namespace selftest
1623
1624 #endif /* CHECKING_P */
1625
1626 } // namespace ana
1627
1628 #endif /* #if ENABLE_ANALYZER */
1629