|
145
|
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 */
|
