|
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 #ifndef GCC_ANALYZER_PROGRAM_STATE_H
|
|
|
22 #define GCC_ANALYZER_PROGRAM_STATE_H
|
|
|
23
|
|
|
24 namespace ana {
|
|
|
25
|
|
|
26 /* Data shared by all program_state instances. */
|
|
|
27
|
|
|
28 class extrinsic_state
|
|
|
29 {
|
|
|
30 public:
|
|
|
31 extrinsic_state (auto_delete_vec <state_machine> &checkers)
|
|
|
32 : m_checkers (checkers)
|
|
|
33 {
|
|
|
34 }
|
|
|
35
|
|
|
36 const state_machine &get_sm (int idx) const
|
|
|
37 {
|
|
|
38 return *m_checkers[idx];
|
|
|
39 }
|
|
|
40
|
|
|
41 const char *get_name (int idx) const
|
|
|
42 {
|
|
|
43 return m_checkers[idx]->get_name ();
|
|
|
44 }
|
|
|
45
|
|
|
46 unsigned get_num_checkers () const { return m_checkers.length (); }
|
|
|
47
|
|
|
48 void dump_to_pp (pretty_printer *pp) const;
|
|
|
49 void dump_to_file (FILE *outf) const;
|
|
|
50 void dump () const;
|
|
|
51
|
|
|
52 private:
|
|
|
53 /* The state machines. */
|
|
|
54 auto_delete_vec <state_machine> &m_checkers;
|
|
|
55 };
|
|
|
56
|
|
|
57 } // namespace ana
|
|
|
58
|
|
|
59 template <> struct default_hash_traits<svalue_id>
|
|
|
60 : public pod_hash_traits<svalue_id>
|
|
|
61 {
|
|
|
62 static const bool empty_zero_p = false;
|
|
|
63 };
|
|
|
64
|
|
|
65 template <>
|
|
|
66 inline hashval_t
|
|
|
67 pod_hash_traits<svalue_id>::hash (value_type v)
|
|
|
68 {
|
|
|
69 return v.as_int ();
|
|
|
70 }
|
|
|
71
|
|
|
72 template <>
|
|
|
73 inline bool
|
|
|
74 pod_hash_traits<svalue_id>::equal (const value_type &existing,
|
|
|
75 const value_type &candidate)
|
|
|
76 {
|
|
|
77 return existing == candidate;
|
|
|
78 }
|
|
|
79 template <>
|
|
|
80 inline void
|
|
|
81 pod_hash_traits<svalue_id>::mark_deleted (value_type &v)
|
|
|
82 {
|
|
|
83 v = svalue_id::from_int (-2);
|
|
|
84 }
|
|
|
85 template <>
|
|
|
86 inline void
|
|
|
87 pod_hash_traits<svalue_id>::mark_empty (value_type &v)
|
|
|
88 {
|
|
|
89 v = svalue_id::null ();
|
|
|
90 }
|
|
|
91 template <>
|
|
|
92 inline bool
|
|
|
93 pod_hash_traits<svalue_id>::is_deleted (value_type v)
|
|
|
94 {
|
|
|
95 return v.as_int () == -2;
|
|
|
96 }
|
|
|
97 template <>
|
|
|
98 inline bool
|
|
|
99 pod_hash_traits<svalue_id>::is_empty (value_type v)
|
|
|
100 {
|
|
|
101 return v.null_p ();
|
|
|
102 }
|
|
|
103
|
|
|
104 namespace ana {
|
|
|
105
|
|
|
106 /* Map from svalue_id to state machine state, also capturing the origin of
|
|
|
107 each state. */
|
|
|
108
|
|
|
109 class sm_state_map
|
|
|
110 {
|
|
|
111 public:
|
|
|
112 /* An entry in the hash_map. */
|
|
|
113 struct entry_t
|
|
|
114 {
|
|
|
115 /* Default ctor needed by hash_map::empty. */
|
|
|
116 entry_t ()
|
|
|
117 : m_state (0), m_origin (svalue_id::null ())
|
|
|
118 {
|
|
|
119 }
|
|
|
120
|
|
|
121 entry_t (state_machine::state_t state,
|
|
|
122 svalue_id origin)
|
|
|
123 : m_state (state), m_origin (origin)
|
|
|
124 {}
|
|
|
125
|
|
|
126 bool operator== (const entry_t &other) const
|
|
|
127 {
|
|
|
128 return (m_state == other.m_state
|
|
|
129 && m_origin == other.m_origin);
|
|
|
130 }
|
|
|
131 bool operator!= (const entry_t &other) const
|
|
|
132 {
|
|
|
133 return !(*this == other);
|
|
|
134 }
|
|
|
135
|
|
|
136 state_machine::state_t m_state;
|
|
|
137 svalue_id m_origin;
|
|
|
138 };
|
|
|
139 typedef hash_map <svalue_id, entry_t> map_t;
|
|
|
140 typedef map_t::iterator iterator_t;
|
|
|
141
|
|
|
142 sm_state_map ();
|
|
|
143
|
|
|
144 sm_state_map *clone () const;
|
|
|
145
|
|
|
146 sm_state_map *
|
|
|
147 clone_with_remapping (const one_way_svalue_id_map &id_map) const;
|
|
|
148
|
|
|
149 void print (const state_machine &sm, pretty_printer *pp) const;
|
|
|
150 void dump (const state_machine &sm) const;
|
|
|
151
|
|
|
152 bool is_empty_p () const;
|
|
|
153
|
|
|
154 hashval_t hash () const;
|
|
|
155
|
|
|
156 bool operator== (const sm_state_map &other) const;
|
|
|
157 bool operator!= (const sm_state_map &other) const
|
|
|
158 {
|
|
|
159 return !(*this == other);
|
|
|
160 }
|
|
|
161
|
|
|
162 state_machine::state_t get_state (svalue_id sid) const;
|
|
|
163 svalue_id get_origin (svalue_id sid) const;
|
|
|
164
|
|
|
165 void set_state (region_model *model,
|
|
|
166 svalue_id sid,
|
|
|
167 state_machine::state_t state,
|
|
|
168 svalue_id origin);
|
|
|
169 bool set_state (const equiv_class &ec,
|
|
|
170 state_machine::state_t state,
|
|
|
171 svalue_id origin);
|
|
|
172 bool impl_set_state (svalue_id sid,
|
|
|
173 state_machine::state_t state,
|
|
|
174 svalue_id origin);
|
|
|
175
|
|
|
176 void set_global_state (state_machine::state_t state);
|
|
|
177 state_machine::state_t get_global_state () const;
|
|
|
178
|
|
|
179 void purge_for_unknown_fncall (const exploded_graph &eg,
|
|
|
180 const state_machine &sm,
|
|
|
181 const gcall *call, tree fndecl,
|
|
|
182 region_model *new_model);
|
|
|
183
|
|
|
184 void remap_svalue_ids (const svalue_id_map &map);
|
|
|
185
|
|
|
186 int on_svalue_purge (const state_machine &sm,
|
|
|
187 int sm_idx,
|
|
|
188 svalue_id first_unused_sid,
|
|
|
189 const svalue_id_map &map,
|
|
|
190 impl_region_model_context *ctxt);
|
|
|
191
|
|
|
192 void on_inherited_svalue (svalue_id parent_sid,
|
|
|
193 svalue_id child_sid);
|
|
|
194
|
|
|
195 void on_cast (svalue_id src_sid,
|
|
|
196 svalue_id dst_sid);
|
|
|
197
|
|
|
198 void on_unknown_change (svalue_id sid);
|
|
|
199
|
|
|
200 void validate (const state_machine &sm, int num_svalues) const;
|
|
|
201
|
|
|
202 iterator_t begin () const { return m_map.begin (); }
|
|
|
203 iterator_t end () const { return m_map.end (); }
|
|
|
204
|
|
|
205 private:
|
|
|
206 map_t m_map;
|
|
|
207 state_machine::state_t m_global_state;
|
|
|
208 };
|
|
|
209
|
|
|
210 /* A class for representing the state of interest at a given path of
|
|
|
211 analysis.
|
|
|
212
|
|
|
213 Currently this is a combination of:
|
|
|
214 (a) a region_model, giving:
|
|
|
215 (a.1) a hierarchy of memory regions
|
|
|
216 (a.2) values for the regions
|
|
|
217 (a.3) inequalities between values
|
|
|
218 (b) sm_state_maps per state machine, giving a sparse mapping of
|
|
|
219 values to states. */
|
|
|
220
|
|
|
221 class program_state
|
|
|
222 {
|
|
|
223 public:
|
|
|
224 program_state (const extrinsic_state &ext_state);
|
|
|
225 program_state (const program_state &other);
|
|
|
226 program_state& operator= (const program_state &other);
|
|
|
227
|
|
|
228 #if __cplusplus >= 201103
|
|
|
229 program_state (program_state &&other);
|
|
|
230 program_state& operator= (program_state &&other); // doesn't seem to be used
|
|
|
231 #endif
|
|
|
232
|
|
|
233 ~program_state ();
|
|
|
234
|
|
|
235 hashval_t hash () const;
|
|
|
236 bool operator== (const program_state &other) const;
|
|
|
237 bool operator!= (const program_state &other) const
|
|
|
238 {
|
|
|
239 return !(*this == other);
|
|
|
240 }
|
|
|
241
|
|
|
242 void print (const extrinsic_state &ext_state,
|
|
|
243 pretty_printer *pp) const;
|
|
|
244
|
|
|
245 void dump_to_pp (const extrinsic_state &ext_state, bool summarize,
|
|
|
246 pretty_printer *pp) const;
|
|
|
247 void dump_to_file (const extrinsic_state &ext_state, bool summarize,
|
|
|
248 FILE *outf) const;
|
|
|
249 void dump (const extrinsic_state &ext_state, bool summarize) const;
|
|
|
250
|
|
|
251 bool on_edge (exploded_graph &eg,
|
|
|
252 const exploded_node &enode,
|
|
|
253 const superedge *succ,
|
|
|
254 state_change *change);
|
|
|
255
|
|
|
256 program_state prune_for_point (exploded_graph &eg,
|
|
|
257 const program_point &point,
|
|
|
258 state_change *change) const;
|
|
|
259
|
|
|
260 void remap_svalue_ids (const svalue_id_map &map);
|
|
|
261
|
|
|
262 tree get_representative_tree (svalue_id sid) const;
|
|
|
263
|
|
|
264 bool can_purge_p (const extrinsic_state &ext_state,
|
|
|
265 svalue_id sid)
|
|
|
266 {
|
|
|
267 /* Don't purge vars that have non-purgeable sm state, to avoid
|
|
|
268 generating false "leak" complaints. */
|
|
|
269 int i;
|
|
|
270 sm_state_map *smap;
|
|
|
271 FOR_EACH_VEC_ELT (m_checker_states, i, smap)
|
|
|
272 {
|
|
|
273 const state_machine &sm = ext_state.get_sm (i);
|
|
|
274 if (!sm.can_purge_p (smap->get_state (sid)))
|
|
|
275 return false;
|
|
|
276 }
|
|
|
277 return true;
|
|
|
278 }
|
|
|
279
|
|
|
280 bool can_merge_with_p (const program_state &other,
|
|
|
281 const extrinsic_state &ext_state,
|
|
|
282 program_state *out) const;
|
|
|
283
|
|
|
284 void validate (const extrinsic_state &ext_state) const;
|
|
|
285
|
|
|
286 /* TODO: lose the pointer here (const-correctness issues?). */
|
|
|
287 region_model *m_region_model;
|
|
|
288 auto_delete_vec<sm_state_map> m_checker_states;
|
|
|
289 };
|
|
|
290
|
|
|
291 /* An abstract base class for use with for_each_state_change. */
|
|
|
292
|
|
|
293 class state_change_visitor
|
|
|
294 {
|
|
|
295 public:
|
|
|
296 virtual ~state_change_visitor () {}
|
|
|
297
|
|
|
298 /* Return true for early exit, false to keep iterating. */
|
|
|
299 virtual bool on_global_state_change (const state_machine &sm,
|
|
|
300 state_machine::state_t src_sm_val,
|
|
|
301 state_machine::state_t dst_sm_val) = 0;
|
|
|
302
|
|
|
303 /* Return true for early exit, false to keep iterating. */
|
|
|
304 virtual bool on_state_change (const state_machine &sm,
|
|
|
305 state_machine::state_t src_sm_val,
|
|
|
306 state_machine::state_t dst_sm_val,
|
|
|
307 tree dst_rep,
|
|
|
308 svalue_id dst_origin_sid) = 0;
|
|
|
309 };
|
|
|
310
|
|
|
311 extern bool for_each_state_change (const program_state &src_state,
|
|
|
312 const program_state &dst_state,
|
|
|
313 const extrinsic_state &ext_state,
|
|
|
314 state_change_visitor *visitor);
|
|
|
315
|
|
|
316 /* A class for recording "interesting" state changes.
|
|
|
317 This is used for annotating edges in the GraphViz output of the
|
|
|
318 exploded_graph, and for recording sm-state-changes, so that
|
|
|
319 values that change aren't purged (to make it easier to generate
|
|
|
320 state_change_event instances in the diagnostic_path). */
|
|
|
321
|
|
|
322 class state_change
|
|
|
323 {
|
|
|
324 public:
|
|
|
325 struct sm_change
|
|
|
326 {
|
|
|
327 sm_change (int sm_idx,
|
|
|
328 svalue_id new_sid,
|
|
|
329 state_machine::state_t old_state,
|
|
|
330 state_machine::state_t new_state)
|
|
|
331 : m_sm_idx (sm_idx),
|
|
|
332 m_new_sid (new_sid),
|
|
|
333 m_old_state (old_state), m_new_state (new_state)
|
|
|
334 {}
|
|
|
335
|
|
|
336 const state_machine &get_sm (const extrinsic_state &ext_state) const
|
|
|
337 {
|
|
|
338 return ext_state.get_sm (m_sm_idx);
|
|
|
339 }
|
|
|
340
|
|
|
341 void dump (pretty_printer *pp, const extrinsic_state &ext_state) const;
|
|
|
342
|
|
|
343 void remap_svalue_ids (const svalue_id_map &map);
|
|
|
344 int on_svalue_purge (svalue_id first_unused_sid);
|
|
|
345
|
|
|
346 void validate (const program_state &new_state,
|
|
|
347 const extrinsic_state &ext_state) const;
|
|
|
348
|
|
|
349 int m_sm_idx;
|
|
|
350 svalue_id m_new_sid;
|
|
|
351 state_machine::state_t m_old_state;
|
|
|
352 state_machine::state_t m_new_state;
|
|
|
353 };
|
|
|
354
|
|
|
355 state_change ();
|
|
|
356 state_change (const state_change &other);
|
|
|
357
|
|
|
358 void add_sm_change (int sm_idx,
|
|
|
359 svalue_id new_sid,
|
|
|
360 state_machine::state_t old_state,
|
|
|
361 state_machine::state_t new_state);
|
|
|
362
|
|
|
363 bool affects_p (svalue_id sid) const;
|
|
|
364
|
|
|
365 void dump (pretty_printer *pp, const extrinsic_state &ext_state) const;
|
|
|
366 void dump (const extrinsic_state &ext_state) const;
|
|
|
367
|
|
|
368 void remap_svalue_ids (const svalue_id_map &map);
|
|
|
369 int on_svalue_purge (svalue_id first_unused_sid);
|
|
|
370
|
|
|
371 void validate (const program_state &new_state,
|
|
|
372 const extrinsic_state &ext_state) const;
|
|
|
373
|
|
|
374 private:
|
|
|
375 auto_vec<sm_change> m_sm_changes;
|
|
|
376 };
|
|
|
377
|
|
|
378 } // namespace ana
|
|
|
379
|
|
|
380 #endif /* GCC_ANALYZER_PROGRAM_STATE_H */
|
