Branch data Line data Source code
1 : : /* Classes for representing the state of interest at a given path of analysis.
2 : : Copyright (C) 2019-2024 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 : 3803 : extrinsic_state (auto_delete_vec <state_machine> &checkers,
32 : : engine *eng,
33 : : logger *logger = NULL)
34 : 3803 : : m_checkers (checkers), m_logger (logger), m_engine (eng)
35 : : {
36 : : }
37 : :
38 : 16148372 : const state_machine &get_sm (int idx) const
39 : : {
40 : 20891164 : return *m_checkers[idx];
41 : : }
42 : :
43 : 598 : const char *get_name (int idx) const
44 : : {
45 : 598 : return m_checkers[idx]->get_name ();
46 : : }
47 : :
48 : 7100638 : unsigned get_num_checkers () const { return m_checkers.length (); }
49 : :
50 : 687489 : 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 : 789258 : 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 : 30908791 : 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 : 177479 : entry_t (state_machine::state_t state,
87 : : const svalue *origin)
88 : 177479 : : m_state (state), m_origin (origin)
89 : : {}
90 : :
91 : 496473 : bool operator== (const entry_t &other) const
92 : : {
93 : 496473 : return (m_state == other.m_state
94 : 482017 : && m_origin == other.m_origin);
95 : : }
96 : 496473 : bool operator!= (const entry_t &other) const
97 : : {
98 : 1004176 : 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 : 1750997 : bool operator!= (const sm_state_map &other) const
126 : : {
127 : 1750997 : 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 : : void clear_all_per_svalue_state ();
150 : :
151 : : void set_global_state (state_machine::state_t state);
152 : : state_machine::state_t get_global_state () const;
153 : :
154 : : void on_svalue_leak (const svalue *sval,
155 : : impl_region_model_context *ctxt);
156 : : void on_liveness_change (const svalue_set &live_svalues,
157 : : const region_model *model,
158 : : const extrinsic_state &ext_state,
159 : : impl_region_model_context *ctxt);
160 : :
161 : : void on_unknown_change (const svalue *sval,
162 : : bool is_mutable,
163 : : const extrinsic_state &ext_state);
164 : :
165 : : void purge_state_involving (const svalue *sval,
166 : : const extrinsic_state &ext_state);
167 : :
168 : 1866487 : iterator_t begin () const { return m_map.begin (); }
169 : 2227068 : iterator_t end () const { return m_map.end (); }
170 : 1079277 : size_t elements () const { return m_map.elements (); }
171 : :
172 : : static int cmp (const sm_state_map &smap_a, const sm_state_map &smap_b);
173 : :
174 : : static const svalue *
175 : : canonicalize_svalue (const svalue *sval, const extrinsic_state &ext_state);
176 : :
177 : : bool replay_call_summary (call_summary_replay &r,
178 : : const sm_state_map &summary);
179 : :
180 : : bool can_merge_with_p (const sm_state_map &other,
181 : : const state_machine &sm,
182 : : const extrinsic_state &ext_state,
183 : : sm_state_map **out) const;
184 : :
185 : : private:
186 : : const state_machine &m_sm;
187 : : map_t m_map;
188 : : state_machine::state_t m_global_state;
189 : : };
190 : :
191 : : /* A class for representing the state of interest at a given path of
192 : : analysis.
193 : :
194 : : Currently this is a combination of:
195 : : (a) a region_model, giving:
196 : : (a.1) a hierarchy of memory regions
197 : : (a.2) values for the regions
198 : : (a.3) inequalities between values
199 : : (b) sm_state_maps per state machine, giving a sparse mapping of
200 : : values to states. */
201 : :
202 : : class program_state
203 : : {
204 : : public:
205 : : program_state (const extrinsic_state &ext_state);
206 : : program_state (const program_state &other);
207 : : program_state& operator= (const program_state &other);
208 : : program_state (program_state &&other);
209 : : ~program_state ();
210 : :
211 : : hashval_t hash () const;
212 : : bool operator== (const program_state &other) const;
213 : 38478 : bool operator!= (const program_state &other) const
214 : : {
215 : 38478 : return !(*this == other);
216 : : }
217 : :
218 : : void print (const extrinsic_state &ext_state,
219 : : pretty_printer *pp) const;
220 : :
221 : : void dump_to_pp (const extrinsic_state &ext_state, bool simple,
222 : : bool multiline, pretty_printer *pp) const;
223 : : void dump_to_file (const extrinsic_state &ext_state, bool simple,
224 : : bool multiline, FILE *outf) const;
225 : : void dump (const extrinsic_state &ext_state, bool simple) const;
226 : :
227 : : json::object *to_json (const extrinsic_state &ext_state) const;
228 : :
229 : : void push_frame (const extrinsic_state &ext_state, const function &fun);
230 : : const function * get_current_function () const;
231 : :
232 : : void push_call (exploded_graph &eg,
233 : : exploded_node *enode,
234 : : const gcall *call_stmt,
235 : : uncertainty_t *uncertainty);
236 : :
237 : : void returning_call (exploded_graph &eg,
238 : : exploded_node *enode,
239 : : const gcall *call_stmt,
240 : : uncertainty_t *uncertainty);
241 : :
242 : :
243 : : bool on_edge (exploded_graph &eg,
244 : : exploded_node *enode,
245 : : const superedge *succ,
246 : : uncertainty_t *uncertainty);
247 : :
248 : : program_state prune_for_point (exploded_graph &eg,
249 : : const program_point &point,
250 : : exploded_node *enode_for_diag,
251 : : uncertainty_t *uncertainty) const;
252 : :
253 : : tree get_representative_tree (const svalue *sval) const;
254 : :
255 : 1170870 : bool can_purge_p (const extrinsic_state &ext_state,
256 : : const svalue *sval) const
257 : : {
258 : : /* Don't purge vars that have non-purgeable sm state, to avoid
259 : : generating false "leak" complaints. */
260 : 1170870 : int i;
261 : 1170870 : sm_state_map *smap;
262 : 8936231 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
263 : : {
264 : 7827524 : const state_machine &sm = ext_state.get_sm (i);
265 : 7827524 : if (!sm.can_purge_p (smap->get_state (sval, ext_state)))
266 : : return false;
267 : : }
268 : : return true;
269 : : }
270 : :
271 : : bool can_purge_base_region_p (const extrinsic_state &ext_state,
272 : : const region *base_reg) const;
273 : :
274 : : bool can_merge_with_p (const program_state &other,
275 : : const extrinsic_state &ext_state,
276 : : const program_point &point,
277 : : program_state *out) const;
278 : :
279 : : void validate (const extrinsic_state &ext_state) const;
280 : :
281 : : static void detect_leaks (const program_state &src_state,
282 : : const program_state &dest_state,
283 : : const svalue *extra_sval,
284 : : const extrinsic_state &ext_state,
285 : : region_model_context *ctxt);
286 : :
287 : : bool replay_call_summary (call_summary_replay &r,
288 : : const program_state &summary);
289 : :
290 : : void impl_call_analyzer_dump_state (const gcall *call,
291 : : const extrinsic_state &ext_state,
292 : : region_model_context *ctxt);
293 : :
294 : : /* TODO: lose the pointer here (const-correctness issues?). */
295 : : region_model *m_region_model;
296 : : auto_delete_vec<sm_state_map> m_checker_states;
297 : :
298 : : /* If false, then don't attempt to explore further states along this path.
299 : : For use in "handling" lvalues for tree codes we haven't yet
300 : : implemented. */
301 : : bool m_valid;
302 : : };
303 : :
304 : : /* An abstract base class for use with for_each_state_change. */
305 : :
306 : 57118 : class state_change_visitor
307 : : {
308 : : public:
309 : 57118 : virtual ~state_change_visitor () {}
310 : :
311 : : /* Return true for early exit, false to keep iterating. */
312 : : virtual bool on_global_state_change (const state_machine &sm,
313 : : state_machine::state_t src_sm_val,
314 : : state_machine::state_t dst_sm_val) = 0;
315 : :
316 : : /* Return true for early exit, false to keep iterating. */
317 : : virtual bool on_state_change (const state_machine &sm,
318 : : state_machine::state_t src_sm_val,
319 : : state_machine::state_t dst_sm_val,
320 : : const svalue *dst_sval,
321 : : const svalue *dst_origin_sval) = 0;
322 : : };
323 : :
324 : : extern bool for_each_state_change (const program_state &src_state,
325 : : const program_state &dst_state,
326 : : const extrinsic_state &ext_state,
327 : : state_change_visitor *visitor);
328 : :
329 : : } // namespace ana
330 : :
331 : : #endif /* GCC_ANALYZER_PROGRAM_STATE_H */
|
