Mercurial > hg > CbC > CbC_gcc

comparison gcc/analyzer/program-state.h @ 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 #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 */