1 /* Classes for representing the state of interest at a given path of analysis.
2 Copyright (C) 2019-2023 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 engine *eng,
33 logger *logger = NULL)
34 : m_checkers (checkers), m_logger (logger), m_engine (eng)
35 {
36 }
37
38 const state_machine &get_sm (int idx) const
39 {
40 return *m_checkers[idx];
41 }
42
43 const char *get_name (int idx) const
44 {
45 return m_checkers[idx]->get_name ();
46 }
47
48 unsigned get_num_checkers () const { return m_checkers.length (); }
49
50 logger *get_logger () const { return m_logger; }
51
52 void dump_to_pp (pretty_printer *pp) const;
53 void dump_to_file (FILE *outf) const;
54 void dump () const;
55
56 json::object *to_json () const;
57
58 engine *get_engine () const { return m_engine; }
59 region_model_manager *get_model_manager () const;
60
61 bool get_sm_idx_by_name (const char *name, unsigned *out) const;
62
63 private:
64 /* The state machines. */
65 auto_delete_vec <state_machine> &m_checkers;
66
67 logger *m_logger;
68 engine *m_engine;
69 };
70
71 /* Map from svalue * to state machine state, also capturing the origin of
72 each state. */
73
74 class sm_state_map
75 {
76 public:
77 /* An entry in the hash_map. */
78 struct entry_t
79 {
80 /* Default ctor needed by hash_map::empty. */
81 entry_t ()
82 : m_state (0), m_origin (NULL)
83 {
84 }
85
86 entry_t (state_machine::state_t state,
87 const svalue *origin)
88 : m_state (state), m_origin (origin)
89 {}
90
91 bool operator== (const entry_t &other) const
92 {
93 return (m_state == other.m_state
94 && m_origin == other.m_origin);
95 }
96 bool operator!= (const entry_t &other) const
97 {
98 return !(*this == other);
99 }
100
101 static int cmp (const entry_t &entry_a, const entry_t &entry_b);
102
103 state_machine::state_t m_state;
104 const svalue *m_origin;
105 };
106 typedef hash_map <const svalue *, entry_t> map_t;
107 typedef map_t::iterator iterator_t;
108
109 sm_state_map (const state_machine &sm);
110
111 sm_state_map *clone () const;
112
113 void print (const region_model *model,
114 bool simple, bool multiline,
115 pretty_printer *pp) const;
116 void dump (bool simple) const;
117
118 json::object *to_json () const;
119
120 bool is_empty_p () const;
121
122 hashval_t hash () const;
123
124 bool operator== (const sm_state_map &other) const;
125 bool operator!= (const sm_state_map &other) const
126 {
127 return !(*this == other);
128 }
129
130 state_machine::state_t get_state (const svalue *sval,
131 const extrinsic_state &ext_state) const;
132 const svalue *get_origin (const svalue *sval,
133 const extrinsic_state &ext_state) const;
134
135 void set_state (region_model *model,
136 const svalue *sval,
137 state_machine::state_t state,
138 const svalue *origin,
139 const extrinsic_state &ext_state);
140 bool set_state (const equiv_class &ec,
141 state_machine::state_t state,
142 const svalue *origin,
143 const extrinsic_state &ext_state);
144 bool impl_set_state (const svalue *sval,
145 state_machine::state_t state,
146 const svalue *origin,
147 const extrinsic_state &ext_state);
148 void clear_any_state (const svalue *sval);
149
150 void set_global_state (state_machine::state_t state);
151 state_machine::state_t get_global_state () const;
152
153 void on_svalue_leak (const svalue *sval,
154 impl_region_model_context *ctxt);
155 void on_liveness_change (const svalue_set &live_svalues,
156 const region_model *model,
157 impl_region_model_context *ctxt);
158
159 void on_unknown_change (const svalue *sval,
160 bool is_mutable,
161 const extrinsic_state &ext_state);
162
163 void purge_state_involving (const svalue *sval,
164 const extrinsic_state &ext_state);
165
166 iterator_t begin () const { return m_map.begin (); }
167 iterator_t end () const { return m_map.end (); }
168 size_t elements () const { return m_map.elements (); }
169
170 static int cmp (const sm_state_map &smap_a, const sm_state_map &smap_b);
171
172 static const svalue *
173 canonicalize_svalue (const svalue *sval, const extrinsic_state &ext_state);
174
175 bool replay_call_summary (call_summary_replay &r,
176 const sm_state_map &summary);
177
178 bool can_merge_with_p (const sm_state_map &other,
179 const state_machine &sm,
180 const extrinsic_state &ext_state,
181 sm_state_map **out) const;
182
183 private:
184 const state_machine &m_sm;
185 map_t m_map;
186 state_machine::state_t m_global_state;
187 };
188
189 /* A class for representing the state of interest at a given path of
190 analysis.
191
192 Currently this is a combination of:
193 (a) a region_model, giving:
194 (a.1) a hierarchy of memory regions
195 (a.2) values for the regions
196 (a.3) inequalities between values
197 (b) sm_state_maps per state machine, giving a sparse mapping of
198 values to states. */
199
200 class program_state
201 {
202 public:
203 program_state (const extrinsic_state &ext_state);
204 program_state (const program_state &other);
205 program_state& operator= (const program_state &other);
206 program_state (program_state &&other);
207 ~program_state ();
208
209 hashval_t hash () const;
210 bool operator== (const program_state &other) const;
211 bool operator!= (const program_state &other) const
212 {
213 return !(*this == other);
214 }
215
216 void print (const extrinsic_state &ext_state,
217 pretty_printer *pp) const;
218
219 void dump_to_pp (const extrinsic_state &ext_state, bool simple,
220 bool multiline, pretty_printer *pp) const;
221 void dump_to_file (const extrinsic_state &ext_state, bool simple,
222 bool multiline, FILE *outf) const;
223 void dump (const extrinsic_state &ext_state, bool simple) const;
224
225 json::object *to_json (const extrinsic_state &ext_state) const;
226
227 void push_frame (const extrinsic_state &ext_state, function *fun);
228 function * get_current_function () const;
229
230 void push_call (exploded_graph &eg,
231 exploded_node *enode,
232 const gcall *call_stmt,
233 uncertainty_t *uncertainty);
234
235 void returning_call (exploded_graph &eg,
236 exploded_node *enode,
237 const gcall *call_stmt,
238 uncertainty_t *uncertainty);
239
240
241 bool on_edge (exploded_graph &eg,
242 exploded_node *enode,
243 const superedge *succ,
244 uncertainty_t *uncertainty);
245
246 program_state prune_for_point (exploded_graph &eg,
247 const program_point &point,
248 exploded_node *enode_for_diag,
249 uncertainty_t *uncertainty) const;
250
251 tree get_representative_tree (const svalue *sval) const;
252
253 bool can_purge_p (const extrinsic_state &ext_state,
254 const svalue *sval) const
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 (sval, ext_state)))
264 return false;
265 }
266 return true;
267 }
268
269 bool can_purge_base_region_p (const extrinsic_state &ext_state,
270 const region *base_reg) const;
271
272 bool can_merge_with_p (const program_state &other,
273 const extrinsic_state &ext_state,
274 const program_point &point,
275 program_state *out) const;
276
277 void validate (const extrinsic_state &ext_state) const;
278
279 static void detect_leaks (const program_state &src_state,
280 const program_state &dest_state,
281 const svalue *extra_sval,
282 const extrinsic_state &ext_state,
283 region_model_context *ctxt);
284
285 bool replay_call_summary (call_summary_replay &r,
286 const program_state &summary);
287
288 void impl_call_analyzer_dump_state (const gcall *call,
289 const extrinsic_state &ext_state,
290 region_model_context *ctxt);
291
292 /* TODO: lose the pointer here (const-correctness issues?). */
293 region_model *m_region_model;
294 auto_delete_vec<sm_state_map> m_checker_states;
295
296 /* If false, then don't attempt to explore further states along this path.
297 For use in "handling" lvalues for tree codes we haven't yet
298 implemented. */
299 bool m_valid;
300 };
301
302 /* An abstract base class for use with for_each_state_change. */
303
304 class state_change_visitor
305 {
306 public:
307 virtual ~state_change_visitor () {}
308
309 /* Return true for early exit, false to keep iterating. */
310 virtual bool on_global_state_change (const state_machine &sm,
311 state_machine::state_t src_sm_val,
312 state_machine::state_t dst_sm_val) = 0;
313
314 /* Return true for early exit, false to keep iterating. */
315 virtual bool on_state_change (const state_machine &sm,
316 state_machine::state_t src_sm_val,
317 state_machine::state_t dst_sm_val,
318 const svalue *dst_sval,
319 const svalue *dst_origin_sval) = 0;
320 };
321
322 extern bool for_each_state_change (const program_state &src_state,
323 const program_state &dst_state,
324 const extrinsic_state &ext_state,
325 state_change_visitor *visitor);
326
327 } // namespace ana
328
329 #endif /* GCC_ANALYZER_PROGRAM_STATE_H */