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