Mercurial > hg > CbC > CbC_gcc

comparison gcc/analyzer/program-state.cc @ 145:1830386684a0

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